I don't know how EC2 instances work in detail, but I imagine there must be a way to get a hold of the host key via an API or something when it's deployed (or maybe at any point) so that integrity could be kept without creating annoyance. I'd be much more comfortable with a solution that, for example, queries AWS over HTTPS before every connection and updates the host key (if necessary).