Windows Messenger always seems to find its way into your system tray one way or another. Remove it once and for all by editing:

c:\windows\inf\sysoc.inf

Look for the line with msmsg and near the end, remove HIDE so the commas have nothing in between. You will then be able to uninstall the program from Add/Remove Programs in the control panel, under Windows Components.

See ya.