I believe the Windows Messenger service has been disabled by default since SP2, if perhaps even SP1. Either way it sounds like a nasty spyware problem. If I were you I would just reformat.