I rarely have encountered something that Ad-Aware or Spybot couldn't get rid of.
Try running them in Safe Mode, and/or stripping out all noncritical processes from your startup. Sometimes spyware will start multiple processes, and one will restart the others if they get shut down (and also keep you from removing their files). If you run a spyware remover in Safe Mode or with startup items disabled, it won't be running at all and you can actually get rid of it.
And, as noted, this should be in the Software forum.