I'm surprised the author tried so many steps - it must have taken ages to resolve the issue. I admire his persistence and documentation of what he found, but others have already posted some good (and often very quick/simple) troubleshooting steps that may have resolved the issue much faster.

I used to work at a nan and pop computer store and dealt with virus infections all day long. I remember the first time I saw TDSS - it stumped me for a few hours. It was about that time that I changed strategy. It seems stupid to me to run rootkit scanners. Trying to check for infections on a machine where the infection already has control just seems like a bad way of handling the situation. We just made it a rule to pull the hard drive, plug it into another machine as slave and run virus scanners from there. We did this for any machine where we suspected a virus was a possibility. Since we didn't have to fix the machines Right Now, we would stop work 20 minutes before the end of the day to look at the PCs on the To Do shelf and would set them up and leave them scanning overnight. This worked wonders. By the morning the scans had run, and half the time the job was complete without needing to do any more work.

As others have mentioned, if you're in a corporate environment then reimaging the machine is probably a good idea. It feels like a cheap/defeatist thing to do and it isn't as rewarding as tracking down the problem, but it sure is fast and effective.