Do theythe servers you are trying to connect to have the same OpenSSH/etc/ssh/sshd_config and/or OpenSSH (and OpenSSL) versions (the bits about identical configs and where are you connecting to seem to be a bit contradictory)? ECDH/ECDSA was introduced in OpenSSH 5.7p1 so if one server is older, it will just ignore the key file. I'm not mentioning differences in configurations, since you explicitly state that those are the same as well.