I had Messenger duplicate all of my contacts. When I restored my computer, I also restored all of the Users data. What I did to fix my duplicates was to delete the C:\Users\<username>\Contacts\<Windows Live Email Address> folder. It is hidden so you will need to change the default settings to show them.
I also deleted C:\Users\<username>\AppData\Local\Microsoft\Windows Live Contacts just for kicks.
When I reloaded Windows Live Messenger, my contacts were back to normal.