Oh my, this could be a PITA for you these things tend to replicate all over your system and some of those redirects for sure will be adding to your nightmares.
The only surefire way of clearing this out is a complete reformat and re-install. There are no shortcuts to peace of mind IMO and really there is no need to mess about with this kind of thing these days.
Then get yourself equipped with some imaging software and make regular images of your OS in future so you can get back to a totally clean and fully working environment within a few minutes of such an occurance. It's much quicker than trying to find and eliminate these kinds of things only to find it's come back in a couple of weeks and Windows System restore just doesn't cut it. In fact many of them things thrive among your System Restore files.
Active Disk Image, Acronis or any of those type of things will cover you. Just get one that will Boot from a DVD/CD image so it doesn't even need to be installed on your system and you can re-prep your drives with it without having to use the infected system.
It happens. Be prepared, and you can be fully back up and running within 10 minutes of something like this happening in future.