Certain infections are very difficult to get rid off from the running OS. They install themselves in the deep innards on Windows and get to decide what goes or not (these are often referred to as "rookits").
In the worst cases, you need to boot the computer from a CD and clean it from there (utilities like SysInternal's ERD can help here, but you'll still need someone who's knowledgeable enough about Windows to do the cleaning).
I haven't looked at recent anti-spyware/virus offerings, but if some of them offer "bootable from a CD" version of their software, that'd be your best bet. Maybe others more familiar with these products can chime in. Me, I tend to clean "by hand," but it's not practical to do over the 'net.
A quick google search gave me this:
Which is apparently a new "bootable" anti-spyware product. Booting from the CD garantees that no infected code is running while you attempt to remove it.
I'm haven't tried it, nor have I read any review, so I don't know if it's any good. They have the right idea though. No trojan, virus or rootkit can defend itself from cleaning if it's not running.
They seem to indicate the the bootable part will clean the worst of the infections, allowing the regular anti-spyware (those that run in the infected system) to complete the clean-up with ease.
Might be worth a try.