So you decided to remove Windows Messenger but Outlook or Outlook Express didn't get the message? To disable the error messages, you need to go to Tools > Options in Outlook Express and in the General tab, untick "Automatically log on to Windows Messenger" and click OK.

If you're using the regular Outlook, go to its Tools > Options. Click the Other tab and uncheck the box in front of "Enable Instant Messaging in Microsoft Outlook".