Eu encontrei o problema. Eu sou o engenheiro de rede, não o cara AD, então eu originalmente não configurei o DNS - eles simplesmente me deram acesso a ele. O problema é que a guia WINS do domínio foi configurada para "Usar pesquisa direta do WINS". Se você clicar em "Avançado", haverá uma configuração "Loookp time-out", que é definida como 2 segundos. Se eu desabilitar o encaminhamento do WINS, ele retornará o NXDOMAIN instantaneamente, como seria de se esperar. yay!