Don't uninstall Windows Messenger, the APIs it uses control other things such as Remote Assistance, Whiteboard and Application sharing, it is never a good idea to remove a windows component either.
A simple way to resolve this problem is to follow the "correct way" guide in
CookieRevised's reply to I am about to rip my hair out over MS Messanger. To do that, Windows Messenger will need to be installed. Also this method allows Windows Messenger to still have it's APIs, but it's disabled properly and won't cause a problem.
After following that guide, your problem should be gone, it worked for me and everyone else I know who's had the problem.