I'm thinking it may be trying to resolve via root hints and you client times out before the DNS server gets the address. The 2nd time you query, the DNS server resolved the address (after your client timeout) and it is now in the DNS cache on the DNS server so it works.
Have you setup each DNS server forwarders to your ISPs DNS server?