This happened to be at the start of the year. A friend has gotten some malware on his PC, then it targets everyone in his contacts, that's why you are getting these messages I believe.
Since with the new Windows LIVE Messenger, you cannot "Block" anyone anymore, you can only appear offline to them. That doesn't solve the issue as you still get thoses messages.
What I did was click on "Help" and then "Report Abuse". Then I told them what happened, and they blocked him through their servers and deleted him. (I deleted him as well, but I still kept getting these messages).
Anyway after that, I haven't received any SPIM (SPAM equivalent on IM). I hope this helped.