Eles vão expirar eventualmente. Antes de fazer alterações, você deve reduzir seu TTL negativo a um valor razoável. O valor é especificado em seu registro SOA para o domínio. Consulte seus servidores para o registro SOA para determinar quanto tempo o tempo limite pode durar.
O valor padrão é documentado como 3 horas e o valor máximo é de 7 dias.
Como você descobriu, não é uma boa ideia consultar seus servidores locais em busca de novos serviços antes que você saiba que eles estão disponíveis em todos os seus servidores de nomes oficiais. Isso pode preparar o cache com uma resposta negativa. Consulta-os primeiro para verificar.