If the contacts computer got compromised then please explain how the contact had all my contacts to give away to the hackers?
Sorry that I didn't retract that clearly enough in my subsequent post.
As for cleaning malware vs. clean install...you have a point about virus/malware education but I think in most cases it's a cost and time based decision.
If you want more help here you might post reports from System Profiler/System Information (installed applications) or the list of processes in Activity Monitor. Someone here might recognize a particular item as malware or an application that asks for access to Contacts when it is installed.
You could also check the system log after adding a new contact to see if anything suspicious happens.
You didn't mention if you checked System Preferences>Security & Privacy>Privacy (tab)>Contacts. Anything there?
One more thing that's not completely clear from your posts...are you saying that the contacts aren't synced with any online services?