Prezado Renato,
Tive um problema idêntico ao seu, com o mesmo Hardware (P III 1.0 Ghz) e
Fedora 8 rodando o BIND 9 em uma rede com mais de 1500 hosts com cerca de
3000 usuários. Resolvi esse problema mudando de distro, coloquei no mesmo
servidor o DEBIAN 4.0 e tá rodando PERFEITAMENTE e esses usuários notaram
rapidamente essa mudança. espero ter ajudado.