Never really been an issue before, try this:
Go to Add/Remove Programs and remove both Messenger PLus! Live and Windows Live Messenger, then go to C:\Program Files\ and delete both the "MSN Messenger" and the "Messenger Plus! Live" folders.
Now, reboot your computer then go to
http://messenger.live.com/ and
http://www.msgpluslive.net/download.php and download them both straight to your desktop (press save as,
not run).
Now install Windows Live Messenger then Messenger Plus! Live.
(I always give this advice to people, simply because it fixes lots of things, not because this is the only thing that I know... I say this because I've been repeating this so many times lately...)