I have the same problem and have done everything that you have AND install SP3.
I did observe that NSLOOKUP will resolve google.com or microsoft.com, but it will not resolve www.google.com of www.microsoft.com. An internet browser will not navigate to any of these addresses, but will go to an IP address that was obtained by a NSLOOKUP.
How about you?
I also observed that when I tried to nslookup www.google.com, it was appeded with my ISP DNS suffix.
I did mess with the DNS suffix settings in the IP network configuration and observed a change for a moment when www.google.com resolved to www.l.google.com. Then the problem returned.