BIND only resolves hostname on the second attempt

[Brian Kendig]

A couple of days ago, my DNS server started behaving oddly: the first
time I try to visit a web site, my browser tells me the server
couldn't be found; if I then go to the same URL a second time, it
works.

My server is Mac OS X 10.3.5 running BIND 9.2.2. My clients are all
Macs, running the Safari web browser, but the problem comes up with
almost anything that tries to resolve hostnames; the game Halo, for
example, gives me a "host not found" error the first time I try to
connect to a network game, but connects on the second attempt. Just
about the only thing which works consistently on the first try is
running 'host' from a command line (as in, 'host www.cnn.com' never
complains it can't find the site).

I ran named at debugging level 2 and tried a query which failed, then
I tried it at debugging level 3 and tried another failed query, and I
posted the logs at 'http://www.enchanter.net/bind-log.txt' (I won't
copy them here, because the stuff logged by -d 3 is long). A few times
in the second example when it can't find 'www.microsoft.com', I see it
append my domain '.enchanter.net' to the end and try that; I assume
this is Safari seeing if the hostname exists locally.

Can anyone please help me figure out what's going wrong, and how to
fix it? What have I misconfigured?