If you're using AMIs from some other third party you should verify that they do the right thing.
i need to automate deployment / reprovisioning of 30 digital ocean servers. as reprovisionined servers frequently use the same ip address, i always run into this. for me I had to disable the check :(
What I've done is added a whitelist to my .ssh/config to disable the alerts only for those hosts. The foo.datacenter.bar.com address (which I use often enough, usually when migrating it between datacenters) still alerts.
And yes, I know I'm living in the 90s what with my datacenters and whatnot. They're kind of like regions... what? Oh... why, you... You kids, get off my lawn!
You're actually better off just baking a shared key into your image. So long as it's a key you generated yourself (not like this Digital Ocean scenario, where the key came from the cloud host), only someone who has already rooted one server can successfully MITM your SSH connections.
Whereas if you ignore host key checks entirely, anyone who gains control of one network hop between you and your servers can own you.
See:
http://www.openbsd.org/papers/asiabsdcon2011_openssh_whats_n...
http://blog.habets.pp.se/2011/07/OpenSSH-certificates
http://en.community.dell.com/techcenter/b/techcenter/archive...
Spend an afternooon to figure this out.