Over the Christmas break, I spent some time trying to eliminate what I believe was a Trojan DNSChanger from my father-in-law's computer. This one was tough; every time I rebooted the problem kept popping up.
So I figured that I had something pretty low in the OS that was preventing the Virus Scans/Spyware removal from being able to remove the stuff. To get past this, I first tried booting into the Trinity Rescue Disk (http://trinityhome.org) and running a virus scan from there. It found nothing.
Interestingly, I did not find any Spyware removal software for a bootable Linux distribution, so I went looking. What I found was the Ultimate Boot CD for Windows (http://www.ubcd4win.com/index.htm). This let me build a bootable CD that was running Windows XP. It did require that I have a copy of my MS Windows XP install disk, but I had that so it was no problem. The really good news is that it came with Spyware/Virus removal tools pre-installed, so it was easy to use this disk to boot into windows, update the Spyware definitions and scan the drive.
In the end, even these steps did not remove this Trojan and I ended up re-installing XP on his computer to eliminate it, but I thought these tools were pretty handy to have in the tool bag.