Make sure that in Windows Messenger Prefs you don't have it checked to start with windows
Another thing you can try is running 'msconfig' (from the run menu type 'msconfig', will not work for win2k) and under "Startup" tab check for 'msmgs', uncheck it if it's checked, apply the changes, then restart your pc
Note: Even after I've tried those 2 things, it still starts up automatically once in a while, so I even went to the registry key reference'd in msconfig for msmsgs (that was for MSN Messenger) and deleted that value, and even after that it still starts up automatically with windows, but at least not always ;-).
