There are a few places that you have to check. One is the OE option already mentioned, and another is in MSN Messenger's options. It has an option to run at Windows startup in one of the tabs (I can't remember which and don't have access right now). I seem to remember another place, but can't think of it at the moment, possibly the internet options control panel.
A more extreme option would be to remove MSN Messenger and use a 3rd Party program like Trillian Pro. These programs are usually a bit easier to control than the Microsoft ones.
goates