As another data point, I'm encountering this issue as well and ssh-keyscan didn't resolve it.
I'm not following the code flow to try to help with this (yet?). I can say that libgit2 doesn't seem to've made any relevant changes since the release of 1.8.1 in May.
