We have noticed that sometimes our instances get a new SSH host key after a reboot action. Finally we've tracked down the error.
When a server boots, it runs cloud-init.
Cloud-init tries to reach various metadata-services, based on an internal list. If contacting a service fails, it will proceed to the next.
Openstack provides metadata (specifically an ID for the instance) both in Openstack format (http://169.254.169.254/openstack/latest/meta_data.json). and EC2 format (http://169.254.169.254/2009-04-04/meta-data/instance-id).
How long it will take before an instance gets a working route to 169.254.169.254 is random and varies.
If you study the instance ID from the metadata information, you'll notice that the EC2-format is formatted like "i-000008f8" while Openstack will use the UUID of the instance, i.e. "b777802f-3277-442c-8c68-bccc6f960e27".
Cloud-init checks the symlink in /var/lib/cloud/instance to see if it matches with the ID it has recieved. If it matches, further provisioning is ignored. If it doesn't match, i.e.if the "wrong" metadata service replies, you can be in a situation where cloud-init will do a full provision, including regenerating the SSH host key, due to cloud-init thinking it is running on a new instance.
You can observe this by looking at the cache-catalog: "ls/var/lib/cloud/instances/" where you'll see two IDs.
We currently don't have a workaround.