Unfortunately, solving this problem isn't easy or obvious. You'd need to use ALIAS / ANAME records, which are only supported by a very few DNS providers (DNSMadeEasy, Rage4, Amazon Route53 if you are hosting on S3). Also, you need to set a low TTL to make sure that you are not caching an old cloud instance's IP address.
The best writeup I found about it is here: http://www.dnsmadeeasy.com/aname-records/