We had a bad infestation of spyware on our home computer that sounds like what you've got. Not even running a browser, stuff would pop up. Neither spybot nor Adaware got rid of it, it kept reinstalling when the computer was booted up. Unfortunately, I can't remember everything that we did to finally get rid of it, I know that I tried running the antispyware software in Safe Mode, but I can't remember if that worked or not. I know there were some specific files that SWMBO deleted manually ('cause she deleted a couple too many).
Cripes, I may have just re-installed Windows...
For regular popups, the Google toolbar works great (it's also nice having the Google search always at the ready). Much, much better than the Yahoo! toolbar. On the old laptop (which was also spyware-infected), I used Opera instead of IE and had no problems (used Firefox for a little while, I just happened to prefer Opera).