Did you reset the trusted sites configuration as well ?
Check what your browser does when you feed it a bogus webpage.. example : www.383283jcjcidjr3k3.com
It should give a nice 404 error that it is unable to find your website and offer you some microsoft search engine ; If it redirects your traffic to some obscure website , then your webbroswer may be compromised.
Does the same thing occur with Mozilla , Phoenix and/or Opera ? (They are FREE and Phoenix does not require setup)