Mac -- I'm running XP-home and with avast! and just the XP firewall engaged. It passes the Shields Up test perfectly. But, XP's firewall doesn't stop outgoing -- only incoming. I also use Spybot and my computer's been clean for over a year.
I've had terrible problems with every McAfee item I ever tried -- installation problems, system slowdowns and failures days later. And, on my machine, McAfee products are a tremendous resource hog.
Did the BlackIce logs show anything? Have you ever tried ZoneAlarm's free version, or, just the XP firewall? Your Gateway should have it since it's running XP.
Obviously, something got into your computer and if it's still there, you need to get rid of it. And, if you're anything like me and you can't find it, you might want to consider wiping your hard drive, reformatting and reinstalling XP. It's a chore, but, at least the Gateway will be clean.
Dave