Do you actually use Microsoft Messenger? If not, junk that software and use iChat or Adium. If you do actually use it (sorry), examine the preferences and see if there is a way to prevent it from automatically signing you in when the system starts, or remove it from your Login Items in Accounts preferences.