Very frustrating and I've been there too. Your suggested method is what I had to do which was a right pain in the proverbial.
Subsequently I set up another address book in Outlook and regularly, before syncing again, delete the entries in the backup and copy the master addresses to it. That ensures that if it happens again I can reverse the process.
I have a Samsung and what I had missed in the syncing program was a simple setting that gave me the option to "Sync as Outlok Data" (or Phone data or notify conflicts) and more imortantly not to allow duplicates.