If I understand you correctly, you want a contact capability distinct from Outlook that you can sync with a PC, which is used by you and your partner.
That sounds like a database app. The easiest one I can think of would be HanDBase. It has a desktop and PPC component and they have a tremendous library of pre-built applications. Surely a contact manager is among them. If KeyContacts has a text file ouput, I would expect you could even export and import your current data.
(
http://www.ddhsoftware.com/handbase_...120.137.146.50)