You could try to do a packet capture of IE's traffic, see what happens. The other guys here are probably right with the issue being related to DNS. You can use nslookup to see what happens with your DNS requests.
To find out which DNS servers are best for you, make yourself a list, and try them with the syntax:
nslookup <server to lookup, eg:
www.google.com> <dns server ip>
As for packet capturing, the only free (GPL) options that come to mind right now are Packetyzer/Ethereal, you'll probably find the Packetyzer GUI easier to handle (the background application is Ethereal in both cases)