Get rid of your PC and buy a Mac. 
In your C:\Program Files folder if you simply rename the “Messenger” folder to anything but “Messenger” I think that should do the trick.
On my system I simply renamed it “Messengeroff”.
It wont delete the files, but it will stop popping up and giving other pieces of ‘toast’ from the bottom left hand side of the screen.
I have tried just about everything but still, it won’t go away. In c:\program files\messenger, the binary is named msmsgsin.exe rather than msmsgs.exe. Further, a search using Windows Explorer failed to find msmsgs.exe, even including hidden and system files and folders.
One web site suggests it might be a virus, but Symantec AntiVirus hasn’t flagged it.
Anybody know anything about the virus/worm angle?
OK, it gets weirder. When I kill it from Task Manager, it restarts within a few minutes.
If you want to completely and “officially” remove it, copy and paste the following in Start Menu->Run:
RunDll32.exe advpack.dll,LaunchINFSection %windir%\inf\msmsgs.inf,BLC.Remove
(Instructions stolen from here.)
Also, if you aren’t running with a firewall (why aren’t you running with a firewall?), you should disable the Messenger Service per QED’s instructions. That was program that let NT-users send pop-up messages to other users or to entire domains. It is now only used for spam.
I can’t check on my machine (since I removed it), but it might be a protected system file. If you delete, rename, or change it, then Windows will periodically check it and restore the original. The archived version might have a funky extension (not .exe).