Service Pack 4 added support for Ranking Data as defined in RFC 2181 section 5.4.1. It, unfortuneatly, could cause the subject problem.
To fix the problem, first upgrade to Service Pack 5.
Insure that all non-authoritative NSs are referenced in Glue records of the authoritative NSs.
If that doesn't fix the problem, use Regedt32 to navigate to:
Edit or Add Value name NoCacheRanking, as a type REG_DWORD, and set the data value to 1.