A General and Mandatory advice when editing the registry: Do Make a Backup of the Registry First.
Three Steps:
1. Open Registry by going to Start->Run->Regedit
2. Browse to the “HKEY_CURRENT_USER\Software\Microsoft\Windows\CurrentVersion\Run\"
3. Delete the “MSMSGS” registry key. Press F5. Thats it. We are done.
Another way to Remove the MSN Messenger Tray Icon is mentioned here.
Avyaya - Tech Rants 
You can also go to Start -> Run, type msconfig, click the Startup tab, and disable the entry from there.
Thanks for the comment.
But, contradicting your point, I assume that MSN Messenger’s Startup Tab checkbox is futile when you need to disable the option. Even after removing the tick from the box, MSN Messenger tray icon would be present.
I have tried it, so I am sure about that.
Pingback: Remove MSN Messenger Tray Icon in XP « Avyaya - Tech Rants
Pingback: How To Remove MSN Messenger Tray Icon | Nirvana's Query
Surfing trying to find a solution. You have it down pat how to remove the Messenger – how do you get it back? My wife’s MSN just disappeared…in processes it is running. Uninstalling and reinstalling same…very strange….