Nós fazemos algo semelhante com um dos nossos sistemas. O DNS é executado a partir do MyDNS, então todos os registros são armazenados no MySQL, tornando as atualizações simples e agradáveis. Os registros TTL também são executados muito baixo, já que uma interrupção de 5 minutos pode ser uma dor.
O sistema basicamente funciona verificando as pulsações a cada poucos minutos e atualizando os registros de acordo.
Não é perfeito, pois um host desativado pode causar uma interrupção nos usuários que recuperam o DNS ou possuem políticas de cache de DNS estúpidas em seus proxies. A única maneira de contornar isso é agrupar os hosts em locais em uma espécie de configuração de alta disponibilidade.