Host Key verification issue

[Mckinnon, Heather (Heather)]

Hello, 
I have script that I run remotely on a server, using ssh config with a 'command'  call in the authorized keys file. I can successfully run this from one of my servers, but when I try from 2 other machines, I receive a Host Key Verification Failed error. 

When I remove the 'command' from the call from authorized keys on the remote server, I can successfully connect to the server. For security reasons, I do not want to do a direct connection to the server. 

I have removed the server name from the known_hosts file and still I cannot get this to work. 

Has anyone seen this issue before? 

In verbose mode, it gets through to the sending of the command, then fails: 

debug1: Sending command: <command parameters>
debug2: channel 0: request exec confirm 1
debug2: fd 3 setting TCP_NODELAY
debug2: callback done
debug2: channel 0: open confirm rwindow 0 rmax 32768
debug3: Wrote 224 bytes for a total of 2037
debug2: channel 0: rcvd adjust 2097152
debug2: channel_input_status_confirm: type 99 id 0
debug2: exec request accepted on channel 0
debug2: channel 0: rcvd ext data 31
Host key verification failed.
debug2: channel 0: written 31 to fed 6

Any idea why this would fail? 

Cheers, and thanks for any insight you may have. 
Heather