MSN Explorer probably has MSN Messenger integrated (sort of like how when you start Outlook Express, MSN Messenger comes on).
Did you try to re-download / install just in case the registry did not update properly?
Now when you say you tried to uninstall but you only saw Messenger 6 there - did you uninstall that one & then download the complete version from:
http://messenger.msn.com/ - or just download the complete version & re-install. It sounds like the registry did not get updated properly.