NOTE: This is not about the common search engine redirect infection.
The issue is with a Windows XP Pro 32-bit machine inside a Windows Server 2003 domain. No other computers on the network have any issues so it is not the firewall or server.
The problem with this XP computer is that after getting infected by some trojans, malware, etc., I could no longer access any search engines (Google, Yahoo, Bing, etc). I will repeat that I don't have the common fake search result redirection issue, these websites are simply not available at all. I also know that it is not a browser issue, because I have cleared all settings on all browsers and I have even downloaded new browsers that were never installed before, such as Chrome and Opera but still no luck getting to those few websites. I don't have a Hosts file inside Windows\System32\drivers\etc so I don't think it is related to that file.
By the way, all infections have allegedly been removed per AVG Pro, Hitman Pro 3.6, Malware Bites Full trial version and ESET online scanner. System restore is not working for any available restore points, so it is not an option. And of course I know reinstalling the OS is an option, please don't suggest that. Thanks.