Mishandles SSH_MSG_USERAUTH_FAILURE
I tried connecting to this server using PuTTY rather than OpenSSH, and found the connection failed for two reasons.
Firstly, the initial SSH_MSG_USERAUTH_FAILURE contains an empty string, where it should contain a list of supported authentication methods – in particular, you're expecting public key authentication, so you should send the string "publickey".
Secondly, a spurious extra SSH_MSG_USERAUTH_FAILURE was apparently sent following the SSH_MSG_USERAUTH_PK_OK during public key authentication.
If I hack the PuTTY source to pretend the server did something different in both cases, I get a successful connection. But I think both are violations of the protocol by this server.
A PuTTY session log is at cheating-log.txt. In that, you can see the initial USERAUTH_FAILURE as incoming packet #0x4: the first four zero bytes should be a nonzero string length followed by that many bytes of string data, which should be a comma-separated string containing at least the component "publickey". Incoming packet #0x6, the second USERAUTH_FAILURE, is completely spurious and shouldn't be there at all. (This is from the locally hacked PuTTY that ignores both those errors.)