Se você não quiser usar o Elastic IP como sugerido por @Ondra, você pode, em vez disso, automatizar o processo de associar novamente os endereços IP recém-atribuídos aos registros Route53 CName.
Aqui está uma postagem no blog que oferece uma maneira:
We have a situation where we use a lot of transient EC2 instances that are part of an integrated set of demonstration machines. They all refer to each other by DNS name that we have set up in a Route53 domain within AWS. For cost reasons, we shut these machines down any time we are not using them. The problem is, every time we boot the machines, we have to go through the grief of re-associating the Route53 CNAMES with the newly-reacquired public DNS and IP entries. Doing this manually is kind of a pain and my nature is always to automated this with command line scripts....