I really hate to add to the white noise on this thread, even though I have the same issues in one form or another. Nevertheless, I'd like to add to my objective experience notes without adding the emotions.
I will only address the Outlook/Windows/PhoneLink use case. Duplicate contacts in outlook (and probably other clients) can be removed very easily and quickly by exporting the entire contact folder to a pst or csv file; delete the contact list and folders entirely from Outlook; import the data you just exported using the "do not import duplicate" option. Bob's your uncle. Worked for me quickly with 10K+ items that once appeared.
PhoneLink produces a category in my outlook contact list that shows up as a folder. Very frustrating since it seems like it should be hidden from the user. After importing the old contact list, that phonelink folder may appear when PhoneLink syncs. Delete it. MS claims that the purpose of this folder is to allow you to segregate contact info in Outlook from what is in PhoneLink. Over time it will reappear.
If you have contact list troubles on your phone, just sync things with outlook (actually exchange) and delete the contact list entries. In time PhoneList will recreate the database from the exchange.
In the past I have deleted the contacts from my phone entirely, disconnected it, and reconnected it as part of this purge. I decided that these steps are ok but aren't needed always.
One of the problems that probably cause the recurrent issues is that MS has redefined what a category is between old Outlook, new Outlook, and versions of PhoneLink. Not being an anthropologist or psychologist, I don't understand why. It doesn't matter. Right now I only have phonelink problems when something else diddles with the exchange database, like if I merged old info into new, and such. But getting over that hump, PhoneLink and Outlook work very well for me in general.