Shoutbox

Try deleting everything in these folders:

for XP, including, but not limited to:
C:\Documents and Settings\your_username\Application Data\Microsoft\MSN Messenger\
C:\Documents and Settings\your_username\Application Data\Microsoft\Windows Live Call\
C:\Documents and Settings\your_username\Application Data\Microsoft\Windows Messenger\
C:\Documents and Settings\your_username\Local Settings\Application Data\Microsoft\Windows Live Contacts\
C:\Documents and Settings\your_username\Local Settings\Application Data\Microsoft\Messenger\
C:\Documents and Settings\your_username\Contacts\
C:\Windows\Temp\MessengerCache\

for Vista/Win7, including, but not limited to:
C:\Users\your_username\AppData\Roaming\Microsoft\MSN Messenger\
C:\Users\your_username\AppData\Roaming\Microsoft\Windows Live Call\
C:\Users\your_username\AppData\Roaming\Microsoft\Windows Messenger\
C:\Users\your_username\AppData\Local\Microsoft\Windows Live Contacts\
C:\Users\your_username\AppData\Local\Microsoft\Messenger\
C:\Users\your_username\AppData\Local\Temp\MessengerCache\
C:\Users\your_username\Contacts\

(cookierevised)

Then restart and try.