Open MSN Messenger.
Click on "Tools", "Options".
General Tab.
CHECK the white square: Automatically run Messenger when I log on to Windows.
Click on OK.
It is supposed to reappear now the next time you reboot.
If not, try to reinstall Messenger.

But it is a good idea to do not enable too much programs at startup to avoid a possible CRASH.
In fact, if you choose to open Messenger WHEN you need it REALLY, not a bad idea after all.