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
Keep Up with TechRepublic