Taken from
this website:
If you are using Windows Vista and Windows Live Messenger:
- Exit Windows Live Messenger
- Open 'My Computer', and in Tools Menu check Show hidden files and folders
- Navigate to these two paths and delete every folder and files in them
C:\Users\
Your Windows logon name\Contacts\
Your Messenger e-mail address
C:\Users\
Your Windows logon name\AppData\Local\Microsoft\Windows Live Contacts\
Your Messenger e-mail address
Replace the parts in bold with your own information.
(If you are using XP or an older version of WLM, the website also includes information on where to find the folders to delete)
I admit I haven't tried this before, and it may not work for you. You can also try simply reinstalling Windows Live Messenger.
/ 
