Good products to get, and all have free versions:
Spybot Search and Destroy
Ad-aware
AVG antivirus

Then, get Firefox -- learn it, live it, and dump Internet Explorer.

Steve, I'm not sure why you had to pay for Spybot or Ad-aware, nor why they didn't work in this case. You may have something new and especially nasty. Try the AVG product before you give up.