Eu conheço algumas possibilidades.
1.) Use um servidor DNS com suporte a banco de dados como PowerDNS + MySQL e apenas atualize o banco de dados quando seu sistema de automação estiver ativo em uma instância (você está usando um sistema de automação, certo?)
2.) Se você não quiser o incômodo de configurar seu próprio servidor, poderá usar um serviço DNS hospedado que forneça uma API (como DNSimple ou Zerigo) e TTLs curtos e envie atualizações para o serviço DNS hospedado por meio de sua API.
Divulgação completa: eu executo DNSimple.
Concordo que você não deve usar IPs elásticos para isso.