If you don't use Windows Messenger, you can delete it using the normal Add/Remove Programs function. The trick is to get it to appear there in the first place, since it is hidden by default.
You need to edit C:\Windows\INF\SYSOC.INF with Notepad.
Props to Jiffy for the following:
>"Under the [Components] heading, you'll see a whole bunch
>of parameters for various windows applets. Some of them
>contain the word "hide." Those particular programs, which
>include windows messenger (msmsgs), Terminal Server,
>Pinball, and others, are installed on your XP system, but
>their entries are hidden from and Add/Remove dialog.
>To remove windows messenger, edit hide out of the line
>so that it looks like this: