Avast + Spybot + Yahoo Anti-Spy + AVG = Epic Win.
I run any one of these four and I can usually get it. Ironically, Yahoo seems to work the best for me, since the guy who keeps giving me spyware changes my Avast and Spybot settings to allow it. AVG sometimes catches it early, but it can pop up at the worst time. (Like, for instance, when your in a massive fight in AOE3...) Basically:
Spybot: A good, solid, all-aroun spyware remover.
Avast: A good backup
AVG: Works great, but the constant updates are stupid annoying.
Yahoo: If the virus persists, use this, it will find it.