It's a little easier to just open Windows Messenger's main UI, click Tools->Options->Preferences, and uncheck both "Run when windows starts" and "Allow to run in the background". It won't auto-launch again.
If you have SP1, you can also remove the Windows Messenger shortcut from your Start menu. Go to Add/Remove Components, and check the box (it's down near the bottom).
You could hack it off your machine as several have suggested, but if you ever decide to install MSN Messenger and use any of its advanced features (such as videoconferencing or app sharing), you'll need to re-install Windows Messenger again for those features to work correctly.