This is not an issue with any kind of timeout value -- it's an issue whereby BSD (or Safari, or Mac OS X, take your pick) gets confused if a DNS server sends back an IPv6 response instead of an IPv4 response (or vice-versa) -- apparently, a LOT of DNS servers are running some derivant of BSD, and it's apparently a flaw in the way BSD handles IPv4 and IPv6 headers: it gets confused sometimes. When you're expecting an IPv4 header and you get an IPv6 header, the system should handle that situation properly and either re-request the header or somehow "know" that the IPv6 header sent back is erroneous and ignore it. Mac OS X, along with many other flavors of BSD, apparently don't do this right.
Enabling/disabling the IPv6 options in the Network pane of the System Preferences doesn't help. Manually entering DNS servers for some has helped, but for others (including myself) it has not.
I recently installed the OS X 10.3.6 update (Delta update on one machine, Combo update on another) and both still experience the "gotta try twice or more" crap.