Is it MSN Messenger or Windows Messenger you are having problems with? MSN Messenger should uninstall easily enough, but Windows Messenger is a little more tricky. If it is Windows Messenger, then here's how to get rid of it once and for all (This applies to Windows XP, by the way):
Click Start > Run... and type the following line into the box:
RunDll32 advpack.dll,LaunchINFSection %windir%\inf\msmsgs.inf,BLC.Remove
Click OK and Windows Messenger will be removed. If you have SP1 installed you might receive an error during the process, but its safe to ignore it ;)
Other than that, I don't know what the deal is, because as I said MSN Messenger should be easily removed.
Hope this helps :)