CentOS 7のduplicity (paramiko)でホスト鍵検証が通らない

サーバを入れ替えてホスト名に対するホスト鍵が変わったサーバ。事前にknown_hostsを編集して新サーバの鍵を追加してあり、OpenSSHのssh、sftpでは正常に接続できる。
また前提としてpython2-paramiko-1.16.1-2.el7 時点ではECDSA鍵は使えないっぽいのでRSA鍵になる。
duplicityでsftp経由でバックアップしようとするとエラーが出る。

BackendException: ssh connection to target.server failed: ('target.server', , )

検索するとホスト鍵の検証を無効化する対処法が出てくるがセキュリティを完全に損なうので言うまでもなく実環境で真似してはいけない。

挙動を見たところ*1、OpenSSHの実装ではドキュメントの通りに一致する鍵が見つかるまでknown_hostsの各行の検証を続けるが、Paramikoでは最初に一致するホスト名しか検証していない雰囲気だった。
今回の場合、旧サーバを落とすまでの一時的な状態として複数の鍵が同じホスト名に対応する状態になっていた。

[target.server],[old.server],[10.0.0.1] ssh_rsa ...
[target.server],[new.server],[10.0.0.2] ssh_rsa ...

target.serverを名前解決すると10.0.0.2(new.server)になりそちらに接続するのだが、old.server側の鍵と比較して不一致のためエラーになっていたようだ。
new.serverという名前で接続するようにしたところ、エラーは出なくなり動作した。

*1:詳細は調べていない