P.S. I use Vista.
To make this work on XP, gmoon stated:
"In XP, you can also disable messenger from "Services", which is found under Performance and Maintenance -> Administrative Tools..."
Antagonizer stated how to remove it from startup in a different way. He said:
1. sign on to windows live messenger
2. click the down arrow that lets you select online, busy, away, etc. and go to the bottom and select "options"
3. Choose the "general" tab
4. uncheck the box beside, "Automatically run Windows Live Messenger when I log on to Windows.
5. Click the 'Accept' button.
...But that, for some odd reason, doesn't work for me. If it doesn't work for you...use my way. :)