Why does the first lookup fail so often? Am I being dumb? (8.2.1, linux)

[Ron Watkins]

We're running BIND 8.2.1, on Redhat Linux 5.2, upgraded to kernel 2.2.10 with
the other ancillary packages. 

What I'm seeing is something that I have seen on ISPs too... an awful lot of
the time, the first lookup for a given name will fail, but later lookups for
the same name succeed.  I get the impression that something is timing out a
bit too soon, and that the answer arrives shortly thereafter.  I'm not sure,
though, where that timeout is occurring, and I don't know if it's fixable.  

Are there any configuration changes I can make that will improve the
first-lookup hit rate?   Any ideas where I might look for the source of the
problem, if this isn't common?  

Some history: we used to run BIND 4.9.something on NT 4.0, running on a
different provider's network, and it seemed to be better about getting names
on the first try.   Before that, we were running Microsoft DNS (bleagh)... but
that was so long ago that I don't remember how it behaved.  It didn't handle
reverse delegation properly for our subnetted Cs, so I tossed it.  

I'm thinking one possibility might be that our provider's net is overloaded --
does that seem at all likely?

Thanks in advance for any ideas,

<<RON>>