I remember the problem was that Windows Messenger did not appear in Add/Remove and this was to let you remove it using conventional methods. It might still work but I don't know if recent service paks have affected this.
To add Messenger to the Add/Remove Programs feature accessible via Control Panel
Navigate to C:\Windows\inf
(If your Windows directory is different, substitute the proper drive letter)
Find the line that reads
Change it to read
Windows Messenger will now appear in Add/Remove Windows Components section of Add/Remove Programs accessible through Control Panel.
Good luck and post if it works.
How do I remove completely// ?Windows Messenger?