http://messenger.jonathankay.com/redir/zapmsngr.asp
try that link
It's a tool to completely uninstall Windows Live Messenger (including any fragments which may have been left behind during a regular uninstall, or if it got corrupted) so that you can do a re-install safely