Shoutbox

I'm not entirely sureif this will work, but you could try going to tools > privacy > and look on the allowed list. Your contacts should still be on the list. Or try clicking on "View..." to see contacts that have added you in the past.

Thinking of it, you can also check your Messenger Logs and Messenger Plus! Logs to revive your contacts.

Messenger Plus! Logs - C:\Documents and Settings\USERNAME\My Documents\My Chat Logs
MSN Messenger Logs - C:\Documents and Settings\USERNAME\My Documents\My Received Files\<name and numbers>\History

USERNAME = your Windows Account Name.
<name and numbers> = Example, chris4158979229. Click one that is appropriate.