Those are all great ideas.... theres just one thing I would add. I too use Ad-aware & Spybot but if you are already experiencing a lot of pop ups I would say.....

Update your Ad-aware, spybot & whatever anti virus you are using (I use AntiVIR)
Switch off 'system restore'
boot up in safe mode
do all 3 scans
restart.

Sometimes without using safe mode you can't get rid of everything and with system restore on the things you do remove are sometimes replaced when you next reboot.

Oh, don't forget to back-up whatever you need when ever you do anything like this... better to be safe than sorry right!