IE no error 404 -> NEW.net search site

A client running Windows XP/Internet Explorer 6 recently complained that when they type in a URL that is incorrect or type in the first part of a URL and press CTRL-ENTER to complete the URL they are taken to a search page provided by NEW.net instead of receiving the Internet Explorer error page.

I know how to fix pirated home page settings but I cannot find what is causing this recent error-page change. I’ve run several adware utilities on the system to detect any spyware/adware that may have caused the change.

Anyone run into this type of behavior and successfully fixed it?