I've just finished battling a similar virus on Dad's laptop. I worked through a similar list to the author and had to persist, because it takes a while to (manually) rebuild that machine.

I was interested that the redirect infected both Bing and Google on IE, Firefox and Chrome.

Eventually got it with the AVG Rescue CD

http://www.avg.com/us-en/avg-rescue-cd