It could still be a server problem too.
It can also be a cache problem...
So, what you could try to do is removing and resetting all the cache of Messenger:
- Go to your security options in Messenger and enable:
Tools > Options > Security > "This is shared computer so don't store my address book, display picture or personal message on it"
- After that sign out and exit Messenger completely:
Right click its systemtray icon and choose "Exit".
- Now, make sure that the cache directories are completely removed from your hard disk. If not, remove them manually (for XP):
\Documents and Settings\your_username\Local Settings\Application Data\Microsoft\Windows Live Contacts\your_windows_live_id\
\Documents and Settings\your_username\Contacts\your_windows_live_id\
Note: some directories might be hidden, so make sure you have enabled the viewing of system and hidden files in Windows Explorer's options.
- If all this is done, sign back in into Messenger. And let Messenger retrieve all the contact information (this could take a bit longer as usual since you don't use any cache now). What is the screen name of this contact now?
- If things are looking ok you might disable the option again which you turned on in step 1.
/ 
