The best thing I ever did was to download a new browser. IE is so vulnerable to attacks.
Get mozilla or opera and use that while you're trying to clean up IE. Both mozilla and opera have pop-up blockers built in them.
Even if IE is clean, I would still have a backup browser.
One time, my IE registry got so screwed up I couldn't even open IE at all. It was a good thing that I had netscape and was able to use netscape to redownload and reinstall IE again.
Now I'm exclusively on Mozilla Firefox and Opera and to this day, I do not worry about spywares or hijackings anymore.
Another thing to remember, read the dialog boxes carefully! Don't just click no to anything, because they might just be the reverse. You think you're saying no to a spyware when in fact you're saying yes to it.