O servidor DNS no seu roteador (ou no seu ISP) provavelmente está armazenando em cache as respostas dos registros existentes, o que geralmente é bom, já que ele tira a carga dos servidores upstream. Dependendo do software em execução no roteador, você poderá desativar o armazenamento em cache ou reduzir esse tempo, mas isso obviamente afetará sua própria rede. Tenha em mente que outros usuários podem sofrer com o mesmo problema. A maneira correta seria apenas diminuir o valor de TTL de suas entradas nos servidores autoritativos para alguns minutos e aguardar o tempo determinado no valor TTL antigo. Após esse período, você pode alterar seus registros e eles também devem ser efetivos em outros servidores de armazenamento em cache dentro do período de tempo determinado no novo valor de TTL. Depois disso, você pode aumentar o tempo novamente para reduzir a carga no servidor autoritativo e fazer consultas mais lentas para os usuários.
Se o problema também ocorrer em novos subdomínios que não existiam antes, você provavelmente não poderá fazer muito, já que provavelmente não terá influência sobre o TTL, já que muitas vezes ele não pode ser modificado pelo usuário normal em serviços DNS usuais.
Para saber qual servidor está armazenando em cache a resposta por quanto tempo, você pode executar nslookup -debug yourdomain dnsserver nos seus roteadores, seus ISPs e em seus servidores DNS autoritativos.