Did you use any of the 3rd party MSN services? I know they ask you to log in with your MSN account, but they're very unreliable. They steal your password when you log in and use bots to send offline messages through your account.
I had the same thing a few years ago. There was a so called program that enabled you to see who's blocking you on MSN. The program asked me to log in with my MSN pass and username. And I did that. Pretty stupid of me.