We just had a problem after a Cisco device recap. The device was on the outside of our network. We could SSH into a device from the outside (i.e. LPZ) but not from the internal network (i.e. MPZ). The SSH traffic goes through a firewall. The outside Cisco device was receiving the SSH request and was logging this message: %SSH-4-SSH2_UNEXPECTED_MSG: Unexpected message type has arrived. Terminating the connection
I am posting this because the solution was to remove the outside device from the known-hosts file on the firewall (a manual process) and then add the device back to the firewall known-hosts file (a manual process). Basically the firewall was using an old SSH hash and the Cisco device wasn't accepting it.