Shoutbox

First let's find out what caused the problem in first place. Probably it was a virus. I'll ask you to to run hijackthis and click on the option "Do a system scan and save a log file" and then post here the log file as a reply to this topic.
Moving on, the solution can be as "simple" as to delete the contacts file:

You must set the folder options and layout on your computer correctly before you can view and delete the contents of your Contacts folder.

Set the folder options:
In Windows XP, on the Tools menu, click Folder Options.
In Windows Vista, on the Organize menu, click Folder and Search Options.
Click the View tab.
In the Advanced Settings list, select Show hidden files and folders, make sure that Hide extensions for known file types is not selected, and then click OK.


Set the folder layout:
In Windows XP, on the View menu, point to Explorer Bar, and then make sure that Folders is checked.
In Windows Vista, on the Organize menu, point to Layout, and then make sure that Navigation Pane is selected.


Delete the contents of the Contacts folder:
In Windows XP, navigate to the C:\Documents and Settings\Your Windows logon name\Contacts\Your Messenger e-mail address folder, and then delete all the files that are in the folder.
In Windows Vista, navigate to the C:\Users\Your Windows logon name\Contacts\Your Messenger e-mail address folder, and then delete all the files that are in the folder.


Delete the contents of the Windows Live Contacts folder:
In Windows XP, navigate to the C:\Documents and Settings\Your Windows logon name\Local Settings\Application Data\Microsoft\Windows Live Contacts\Your Messenger e-mail address folder, and then delete all the files that are in the folder.
In Windows Vista, navigate to the C:\Users\Your Windows logon name\AppData\Local\Microsoft\Windows Live Contacts\Your Messenger e-mail address folder, and then delete all the files that are in the folder.

Close Windows Explorer and try to sign in to Messenger again.