Tenha em mente que os clientes DNS armazenam em cache respostas negativas, bem como as positivas. Talvez isso seja responsável por algum tempo que você espera em registros recém-adicionados?
Você pode configurar o tempo de armazenamento em cache negativo em seus clientes:
HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Services\DNSCache\Parameters
NegativeCacheTime value (DWORD). The default data is 300 seconds. If you do not want negative responses to be cached at all, set the value of NegativeCacheTime to 0.