Have you also tried Spybot S&D and Spysweeper? One thing I've found is that Adaware, Spybot and Spysweeper compliment each other, catching things the others miss and vice versa. I also use AVG from Grisoft. Free, daily updates, and is very good at catching things as well. I tend to go with freebies, although Spysweeper only has a 30 day trial, which should be more than long enough to get rid of a lot of nasties.
One system I cleaned for a lady from my SO's work had over 800 hits on Spybot, 700 hits on Adaware, 300 hits on Spysweep, and AVG had none. I ran them in that order.