Doc,
This is interesting and many thanks for the research. I too have had similar experiences, though not in a "controlled" situation such as your VM, it was as always pulling these things out from a system at work a user had got screwed up or a "harry homeownser" I was doing a good deed for.
Since you limit the topic to spyware tools like Adaware and Spybot and didn't cover quasi-spyware related tools and/or virus removal tools such as S-t-i-n-g-e-r (ugh horrible choice to rename to) or MS's MRT, I'll only throw in my two cents with respect to two of the tools you covered that I use most, Adaware and Spybot.
1) If you know the system is really messed up its best to start from safe mode. Then go into task manager and try to kill any suspect looking thing if you can before continuing. Then also try to stop any unnesessary services.
2) I have found it is possible to run both of these spyware removal apps from a network share or just plain copied into a directory to make a stab at getting a system under control again. Agreeably this defeats some of the utilities in each, but as you pointed out stepping through the install prompts and setup is tedious on a system clocking near 100% of its CPUs to crapware.
3) As I think you and others have posted here and the tools have on their respective websites there are also silent command line switches that can do a scan or auto remove without stepping through the dialogs.
4) As you found, it becomes necessary to resport to manual pulling of some stubborn spyware. I especially enjoy typing a for-in-do loop in a spyware directory and calling regsvr32 to unregister the offending *.dll's.
Bottom line I guess is as you point out, none of the current removal tools are up to the job on theri own and especially when used "out-of-the-box" in the hands of "Harry homeowner". It does take experience for a really messed up system to come clean.
I recall one system belonging to a friend of my wife's that I called the "Petri Dish", it had everything growing in it, even some classics. It took 3 hours to clean, update and get AV, firewall and everything working again. Would have been easier to format and reinstall, but I wanted to see for myself if it could be done.
mole
_________________________
mole
Who is John Galt?