Either uninstall thru "windows components",or open messenger,tools/options,
uncheck the area "have messenger auto start" uncheck,"start on windows start
up"..There's only two boxes to uncheck.
You should go to 'tools' > 'option' > 'preferences' in Windows
Messenger and disable all the four items in the 'general' para.
Then exit WM and if you reboot it should be gone.