Nslookup not consistently resolving

I have set up a Windows NT 4.0 server running as a dns server. Nslookup resolves fine on my network, but as far as external(internet) requests it only resolves some of the time. The behavior is the same on my linux machines, as it is from my windowsboxes.
I either get ‘dns server’ can’t find : non-existent domain, or if it does resolve it does so as a non-authoratative answer. It will occaisionally resolve correctly(maybe 5% of the time). I cannot determine what the problem is. Common sense says that if nslookup can resolve even once, then my configuration is fine. Is nslookup something that typically is very inconsistent, should I be worried about it?
All my internet traffic does appear to be fine, browser, ftp, whatever.I do have a reverse zone configured, as I know reverse lookup is an important issue.
Your help is apreciated, Thanx- Keith Auerbach