I dont remember the original hotmail as i am using live since long time.
I also had a similar problem. What I did was to go to individual contact , click edit and then delete it. Just try to edit single single contacts and delete it. It worked for me some 3 months back.