Ok. Try and remove everything that is Messenger related. Here is how.
Go to Add/Remove Programs and uninstall Windows Live Messenger.
Now, manually delete the following folders,
after you've uninstalled WLM.
Note: This will delete any custom content you have (emoticons, DPs, etc). Use
BackUp MSN if you want to backup your custom content.
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:\Program Files\MSN Messenger\
C:\Windows\Temp\MessengerCache\