Try this:-
go to start-> run and thype this %userprofile%\local settings\application data\microsoft
locate the windows live contacts folder and delete it
I found this in this link.
http://www.microsoft.com/communities/newsgroups/en-us/default.aspx?dg=microsoft.public.windows.live.messenger&tid=4bfd5c16-2f20-44fd-a229-709d18b48b10&cat=en_US_CA72C644-5AB9-1B63-DA37-E285FB59341F&lang=en&cr=US&sloc=en-us&m=1&p=1
Hope it works for u.