A General and Mandatory advice when editing the registry: Do Make a Backup of the Registry First.
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.