Not everything/ every problem is caused by a virus.
You could try completely removing your contact cache store
Try this:.
To do so, shut down Messenger, then click Start, then
Run, type:
%appdata%\Microsoft
Right-click the MSN Messenger folder and choose Delete. Then
restart Messenger and see if
the problem has been corrected.