The solution: It works both via MSN Messenger and Windows Messenger:
-Downloaded the latest version of termsrv.dll and replaced the old
file.
http://www.dlldump.com/download-dll-.../download.html
-Changed this registry setting to : 0 (it was set to 1)
HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Windows
NT\CurrentVersion\Winlogon\DontDisplayLastUserName

Cheers!
NeilSanner