This can happen when you upgrade Messenger sometimes.
As you said, you can't uninstall the old version using Add/Remove programs because it's not in the list
I use a script to remove the old Messenger, you just run it, reboot and the old version is gone
I can send you it if you like?

cheers, Alan