I think I'm adding a new step to my acceptance procedures for cloud servers: always re-generate the ssh host key. Providers aren't always doing their homework and making sure that the ssh host keys on their customers servers properly created.