I am experiencing exactly the same issue. The initial lookup seems to fail but then if the page is refreshed or if you manually type in the URL (incidentally the school website which is hosted externally) it loads the page absolutely fine.
I have checked the group policies which seem fine and all of the above. We are using smoothwall but my machine has a proxy exception and it is still happening which makes me think it's a DNS issue. Any ideas...
I had to delete and re configure my DNS settings. Then problem was fixed. As srochford suggested please check.