Proflie Problems

A user at my job has been having problems with his Internet Explorer and Outlook. When he logs onto any browser but IE he is able to search the web. IE will not let him. He also cannot send e-mail through Outlook. He is set up as Administrator over three PCs running Windows 2000. He can however go to the other two PCs and log onto the IE6 with no problems and send e-mail. We tried downloading the SP for IE6. We also blew away his proflle and created a new one. Neither worked. Whats going on here?