nslookup Got recursion not available from... trying next server

[vr]

I'm having a query problem and hope I'm at the right mailing list...

I get a "recursion not available" message intermittently when using 
nslookup. The message will appear on the first query, presumably to 
un-cached IP/hostname and subsequent queries to the same IP/hostname 
will succeed without the message.

The client is Debian Lenny, package 1:9.6.ESVR1+dfsg-0+lenny2.
The clients /etc/resolv.conf has two nameserver entries pointing to 
two internal DNS servers which are Windows 2003SP2. Both the client and 
the servers are on the same subnet and switch as the client performing 
nslookups. I have confirmed the two DNS servers have recursion enabled.
Changing the order in the Debian clients resolv.conf does not modify 
or correct the behavior of nslookup.

Using another Debian Lenny client to query the Windows 2003 servers 
reproduces the message in the same intermittent fashion.

Using other Debian Lenny clients to other Debian BIND servers (unsure 
of package version) on other networks reproduces the "recursion not 
available" message. (always with nslookup)

I originally stumbled upon this query problem because my Postfix 
instance would also intermittently fail lookups and log them to 
mail.log. I found information in the Postfix archives that Postfix uses 
the libraries of the host so I turned to nslookup to troubleshoot 
queries.

I have not been able to receive the "recursion not available" message 
while using dig.

Is this "recursion not available" message a known issue?

Since I'm seeing this recursion message in more than one environment, 
how would I, and my installed applications, get more consistent 
successful queries out of the respective systems?