Possibly. In 2010 MobileMe contact and calendar syncing was rendered nonfunctional for 1000's of users based on "fb:" hyperlinks inserted into contacts and events by facebook. Though, the bug was on server side, not in the users' apps. Still, if some of your existing contacts have any xml-ish bits of text, they could be relevant to the issue.One more thought. Would there be any chance it has anything to do with a non-Mac mail reader (postbox) accessing contacts?
I've had a bug in Notes app, which I have hooked up to Google (Exchange) sync, for a few months where backspacing a line indent within an open note deletes the entire paragraph above that indent. Haven't been interested enough to troubleshoot it.
There are 3rd party apps for everything Contacts does, and that can scan your contacts for duplication / formatting problems. Personally, I would just try one of those out. Troubleshooting sync in Contacts to isolate between app / account / data as the culprit is nightmarish.