Since it is related to an application, you may want to run +Repair Disk Permissions+ in Disk Utility, if you have not recently.
Have you checked the preferences for MSN Messenger? I don't use that program so I can't check it myself, but there may be a setting there for selecting the alert sound to play, and to turn off that particular alert sound.
You can also try moving the preference file for MSN Messenger to the Desktop (with the program NOT running), to allow the program to create a fresh file the next time it runs. I don't know the exact name of the file, but is should be here
<user home folder>/Library/Preferences/
and have a name that indicates it is for MSN Messenger. If you lose some settings that you need, you can put the file back.
If sound is generally working (such as for playing music in iTunes), I don't think it is related to Audio Midi Setup utility, although I'm not sure why the settings there are disabled.