It could be spyware, but that usually wouldn't affect anything but IE like this. Still, can't hurt to check.

There's also every chance that since it happens in every browser, that it's a problem with your ISP's DNS system. Call up their tech support and make sure you have all the settings correct and see if you can't convince them to get someone to look over their DNS server configs.