Hi Nathan. There are several ways to get rid of Messenger. One, if you are running XP, is to make it available in the Add and Remove Windows options.
To do this go to Run- and enter C:\Windows\inf\sysoc.inf
Then scan down to the entry msmsgs=msgrocm.dll take out the word Hide from between the two commas, but leave the commas there. Then save and close.
Go to the Add/Remove Windows components and Windows Messenger will be an option. Remove both the ticks and Save.
You might find that the ticks keep reappearing, but keep taking them out and they will go eventually. Make sure that Messenger isn't running when you remove the ticks. If ever you want it back again simply replace the ticks.
If you are successfull the option in Outlook will disappear.