if you are talking about the MSN messenger that came already installed on your Windows XP machine....
you actually can't uninstall it. the program is integrated into the OS. (microsoft is tricky, aren't they

)
the only thing you can do, unfortunately, is disable it so it can't run.
go to
Start > run > type
services.mscfind the entry "Messenger" and disable it, and/or do what TonyKlein suggested
if however, you installed Windows Live Messenger yourself (from their website) then you should be able to get rid of it.
to get it to 'reappear' back into the add/remove program list, simply go back to their website and reinstall it. (like Jimemy said) this will "refresh" the install.
after that, it should appear in the add/remove program list, and you should be able to safely uninstall
though I think what you are dealing with, is the version that is stuck on your computer