I was setting up a new user's access on a machine today, and went to test his ability to ssh into another machine. Since the test server was configured to use One Time Passwords, I didn't want to waste one of the passwords in a test, and used jexec to bind to the user's shell instead of using SSH to log in. The problem here became any time I went to ssh to a machine, I received the error: Host key verification failed.
After a little digging around, I realized that when switching to an account through jexec, it does not bind the shell to your tty. This was a problem because since the account was for a new user, there was no known_hosts file yet, and ssh needed to prompt me to accept the server's key before continuing. Since it couldn't collect the input, it simply failed. After using SSH to connect to his shell instead, I was then able to SSH normally again, with no errors.
An alternative approach could have been to place a proper known_hosts file in his ~/.ssh/ path that was already populated with proper keys, but SSH is a much more straight-forward method and the recommended proceedure to use.