[princeG]

Another possible solution:

Delete you handshaking policy cache:
Exit Messenger completely (this means right clicking the Messenger tray icon and choosing Exit).

Open your registry editor (Start > Run > regedit.exe) and navigate to:
for Messenger 8.0: HKCU\Software\Microsoft\MSNMessenger
for Messenger 8.1: HKCU\Software\Microsoft\WindowsLive\Communications Client

Once there, you must remove the following subkeys:
for Messenger 8.0: Policies
for Messenger 8.1: Shared

Close your registry editor and restart Messenger.