For those of us out in the trenches, week in and week out, cleaning this stuff up year after year, the issue(s) you raise regarding the complete removal of malware is nothing new. Malware is getting more and more sophisticated, for example a piece of work that started out as PAV (Personal Anti Virus) and its "relatives" AntiVirus 2009, etc.

This stuff's defeating ANY installed AV/AS apps on the computer if it's hooked in long enough (a few hours?) to the OS. The .exe's and where they run from change constantly. Every week. And once this stuff's getting into a given PC, they are tough to find and tougher to defeat, though I am picking up some new tricks as I go along. Booting to Safe Mode w/ Command Prompt is the best thing for manually removing some malware. Run taskmgr, then HJT and ass't apps from a USB drive, which is likely to get infected in the process.

Any chance of completely removing it involves running reg cleaners (Ccleaner has a good one), clearing out temp files, particularly ones that don't want to be deleted, after removing a primary infection. As well as clearing out restore points and any other nooks or crannies this cr@p hides in. So, for me, I don't care anymore if a given AV/security app can clean out everything. Because I know it can't. So I use a repertoire of security apps to cover as many bases as possible. The trade-off is what do you want to live with? A clean Windows install sans user's apps and data. Or the PC close to what it was pre-infection.

It begs the question as to how one assesses the risk of registry entries and temp files left behind? As for the cloud, in some ways it is nothing new. In other ways, it is, but I digress...