Hi Ajax.
I used to have this problem as well, you want the good news or the bad news first? Ad-aware is good but you need a few more things in place to prevent this type of thing.
I know my Start-->Settings-->Add/remove programs list off by heart, any crap I find in there I uninstall asap (about once a week).
Run ad-aware v6. It has an option to run before windows starts up. Use that, it cleans more ads.
Get Regcleaner or any other good registry cleaner and run that regularly, about once a week.
Get a good pop-up killer and firewall. I use Zone-Alarm pro.
Turn off cookies. It means you have to remember your own usernames and passwords, but it also prevents a lot of other nasties.
Now for the bad news. I once got this bloody toolbar from some scandinavian site which sells box sets of horror movies. Man I just couldn't get rid of this thing. I eventually uninstalled IE and deleted every file I could find that had anything to do with IE, including the whole messenger directory, which of course prompted windows to have a fit. I re-installed messenger and then IE. Yeehaa, no toolbar, but now IE was as responsive as a bulldog who has sniffed a bone. Man it was slow. 3 -4 minutes to find a site. I fortunately for me am one of those people who can rebuild his machine at the drop of a hat. So did that and instituted the regime mentioned above. Not had the problem since.
Good luck.
Of course I don't look busy.....I did it right the first time.
