It shouldn't be this complicated, but this is the hack I found to keep MSN Messenger from launching at startup.
Start -> Run
Type: gpedit.msc
The Group Policy Object Editor will open. Drill down to:
User Configuration > Administrative Templates > Windows Components > Windows Messenger
Double click the object "Do not allow Windows Messenger to be run" and choose the Enabled option. Click Apply.
Double click the object "Do not automatically start Windows Messenger initially" and choose the Enabled option. Click Apply.
You will need to reboot your machine to see this take effect.