The messages are sent using the messenger program built into MS Windows.
This site has a little explanation and a small guide to get rid of the problem:
click here
For those that don't like links: one way seems to be to block port 135 in your firewall.
(other ways are stated in the article)
I hope this helps you!
If you still have problems, please post them here...
Silvy
Disclaimer: I don't have any such problems and have thus not tried any of these workarounds.
EDIT: There is no need for them to spread virus-like programs AFAIK, they can just send those messages directly from their systems to your PC. The messenger is probably meant as a way a system-administrator can send all machines on the company network a message (like "Network going down in 5 mins"). Too bad MS Windows allows such messages to come from across the world, without an easy way to block them...