Shoutbox

\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\

Exit WLM and delete those two folders and it will force your WLM to re-download your contacts from the server, which may or may not re-synchronise your reverse list (and therefore contact cleanup). 

All this will remove is stored display pictures and log-in names for contacts who have been online.  It's worth a try, but it doesn't appear to have worked for aznmachine