I'm inclined to rule out spyware seeing as you have already checked for that so this might work:

Click Start and then click Control Panel.
Click Performance and Maintenance. (If you can't see the Performance and Maintenance icon, you're probably using Classic View so switch to the other view.)
Click Administrative Tools.
Double-click Services
Double-click Messenger.

In the Startup type list, choose Disabled from the Startup type list in Messenger Properties.

Click Stop, and then click OK.

If that doesn't help post back and we'll see what else it might be!

It's not often we see a Mac user here as you can imagine. I use both Windows and OS X.
What type of Mac do you have?