@Mart: the hostkey is checked only at the beginning of the connection. Even if it does change in the middle of the connection (imo impossible for common OpenSSH server), you wouldn't notice the change. Something does not match in your post. Also, isn't your server load balanced? If it is, you can list hostkeys of all server instances in the
-hostkeyswitch. If you need out help, please post logs.