Disable the Windows messenger service, You should also disable NetBIOS, and preferrably block UDP port 135 and TCP 137 + 139 (use Windows' firewall thingy if you haven't got a real one). If you've got a Windows/SMB network then that will break from doing the latter, but you shouldn't have that on an interface to the Internet anyway - but as we know even "professional" Windows versions like NT/XP come with absolutely everything enabled out of the box.
There was some hullabaloo on Slashdot over this recently, but their so-called search function is even more broken than usual, so I can't find it now.
Google comes up with e.g.
these instructions on how to disable messaging.
