Shoutbox

This might not be the solution, but it is worth to try:

Delete your Contacts Cache folder...

You will loose nothing with this. The only thing which you might notice is a slightly longer delay in logging in the next time you start up Messenger (since the cache list needs to be rebuild).

In order to do this you first need to make sure you can see hidden files and system files in Windows Explorer:

1. Start Windows Explorer (or press <WIN>+<E> for quick shortcut)
   
2. Go to Tools > Folder Options > View tab
   
3. in the Advanced Settings list, tick "Show hidden files and folders"
   
4. in that same Advanced Settings list, untick "Hide extensions for known file types"
   
5. Press Ok.

To delete your cached directories:

1. With Windows Explorer, navigate to:
   C:\Documents and Settings\your_windows_login\Contacts\your_msn_mail
   
   
2. Delete the entire subdirectory named your_msn_mail.
   
   
3. Now navigate to the folder:
   C:\Documents and Settings\your_windows_login\Local Settings\Application Data\Microsoft\Windows Live Contacts\your_msn_mail
   
   
4. Delete the entire subdirectory named your_msn_mail.