I just found this recently and it works.
Open C:\Windows\Inf\Sysoc.inf in Notepad.
Find the line under [Components] that reads "msmsgs=msgrocm.dll,OcEntry,msmsgs.inf,hide,7"
Change this to "msmsgs=msgrocm.dll,OcEntry,msmsgs.inf,,7"
i.e. remove "hide" from between the commas.
Save the file and go to the Windows components portion of Add-Remove. Messenger will now show up as removable.
Is there a simple way to remove windows messenger from my Windows XP system?

Chowhound
Comic Vine
GameFAQs
GameSpot
Giant Bomb
TechRepublic