mrcleanpc.com hijacker?

Well you got it working, good for you. Some advice: Since we don't really know what the infection was I would do some more scanning. You say malwarebytes doesn't find anything. What are you using for an Anti Virus? You could always download Microsoft Security Essentials and scan with that. You could try free Avast. and when your are done scanning turn them all off except the one you prefer. You could even uninstall the ones you don't want. One other option you have is from an adminstrator command prompt* window run "mrt" (no quotes).

*Right click Command Prompt in Accesories and select "Run As Admin" for an elevated command prompt

Agent Zach said:

I know that the issue has been solved, but does anyone think that his "hosts" file may have been compromised?

If the issue was appearing with every browser (including newly installed ones), the hosts file seems like it may have been the suspect...

This is a good idea and can't hurt to look :)

callmemrv, this guide will help you check your host file, if you are unsure of anything then please don't hesitate to ask
Hosts File : Use in Windows 7 / Vista

An untouched host file would look something like this:

Image was used from the above tutorial

Regards,
JDobbsy1987