Question : Problem: Unusual SSH Behavior - Disconnecting: Bad packet length on first connection.  Then it works.

I have a problem with freeSSHd 1.2.1.  Basically, it's installed on many (75+) Windows 2003 Web Edition servers.  Each of them was installed by command-line as such:
freeSSHd.exe /VERYSILENT /Service /KeyGen /NOICON /SUPPRESSMSGBOXES

After the install, I copy an INI file which has the user / password / port settings / etc.  I copy this into the install directory ("C:\Program Files\freeSSHd\FreeSSHDService.ini").

Here's the problem... (IP changed since it's live)
I am on linux trying to SSH to these Windows machines.  Upon connecting the first time, I get this:
"ssh [email protected]
The authenticity of host '111.111.111.111 (111.111.111.111)' can't be established.
RSA key fingerprint is 86:9a:f8:55:be:f6:2b:c2:75:2f:c7:2a:47:a6:f5:96.
Are you sure you want to continue connecting (yes/no)?"

I type "yes", hit enter and am met with this result:
"Warning: Permanently added '111.111.111.111' (RSA) to the list of known hosts.
1cdb 2b3a cf41 d2fd b0c1 bd97 c17e e4bb

Disconnecting: Bad packet length 484125498."

If I try to connect again, it works.  It gets to the password prompt (and I am able to log in)
"[email protected]'s password:"

Why does it take two attempts to login successfully?  Even weirder, if I clear my known hosts file, I get the same problem (connecting twice fixes it)
rm ~/.ssh/known_hosts

Here is a dump of when I do the ssh connection from the linux client with -vvv to capture all the details:
ssh -vvv [email protected]
OpenSSH_3.6.1p2, SSH protocols 1.5/2.0, OpenSSL 0x0090701f
debug1: Reading configuration data /etc/ssh/ssh_config
debug1: Applying options for *
debug1: Rhosts Authentication disabled, originating port will not be trusted.
debug2: ssh_connect: needpriv 0
debug1: Connecting to 111.111.111.111 [111.111.111.111] port 22.
debug1: Connection established.
debug1: identity file /home/user/.ssh/identity type -1
debug1: identity file /home/user/.ssh/id_rsa type -1
debug1: identity file /home/user/.ssh/id_dsa type -1
debug1: Remote protocol version 2.0, remote software version WeOnlyDo 2.0.6
debug1: no match: WeOnlyDo 2.0.6
debug1: Enabling compatibility mode for protocol 2.0
debug1: Local version string SSH-2.0-OpenSSH_3.6.1p2
debug1: SSH2_MSG_KEXINIT sent
debug1: SSH2_MSG_KEXINIT received
debug2: kex_parse_kexinit: diffie-hellman-group-exchange-sha1,diffie-hellman-group1-sha1
debug2: kex_parse_kexinit: ssh-rsa,ssh-dss
debug2: kex_parse_kexinit: aes128-cbc,3des-cbc,blowfish-cbc,cast128-cbc,arcfour,aes192-cbc,aes256-cbc,rijndael-cbc@lysator.liu.se
debug2: kex_parse_kexinit: aes128-cbc,3des-cbc,blowfish-cbc,cast128-cbc,arcfour,aes192-cbc,aes256-cbc,rijndael-cbc@lysator.liu.se
debug2: kex_parse_kexinit: hmac-md5,hmac-sha1,hmac-ripemd160,hmac-ripemd160@openssh.com,hmac-sha1-96,hmac-md5-96
debug2: kex_parse_kexinit: hmac-md5,hmac-sha1,hmac-ripemd160,hmac-ripemd160@openssh.com,hmac-sha1-96,hmac-md5-96
debug2: kex_parse_kexinit: none,zlib
debug2: kex_parse_kexinit: none,zlib
debug2: kex_parse_kexinit:
debug2: kex_parse_kexinit:
debug2: kex_parse_kexinit: first_kex_follows 0
debug2: kex_parse_kexinit: reserved 0
debug2: kex_parse_kexinit: diffie-hellman-group1-sha1,diffie-hellman-group14-sha1
debug2: kex_parse_kexinit: ssh-rsa,ssh-dss
debug2: kex_parse_kexinit: aes128-cbc,3des-cbc,blowfish-cbc,aes192-cbc,aes256-cbc,rijndael128-cbc,rijndael192-cbc,rijndael256-cbc,rijndael-cbc@lysator.liu.se
debug2: kex_parse_kexinit: aes128-cbc,3des-cbc,blowfish-cbc,aes192-cbc,aes256-cbc,rijndael128-cbc,rijndael192-cbc,rijndael256-cbc,rijndael-cbc@lysator.liu.se
debug2: kex_parse_kexinit: hmac-sha1,hmac-sha1-96,hmac-md5,none
debug2: kex_parse_kexinit: hmac-sha1,hmac-sha1-96,hmac-md5,none
debug2: kex_parse_kexinit: zlib,none
debug2: kex_parse_kexinit: zlib,none
debug2: kex_parse_kexinit:
debug2: kex_parse_kexinit:
debug2: kex_parse_kexinit: first_kex_follows 0
debug2: kex_parse_kexinit: reserved 0
debug2: mac_init: found hmac-md5
debug1: kex: server->client aes128-cbc hmac-md5 none
debug2: mac_init: found hmac-md5
debug1: kex: client->server aes128-cbc hmac-md5 none
debug2: dh_gen_key: priv key bits set: 133/256
debug2: bits set: 522/1024
debug1: sending SSH2_MSG_KEXDH_INIT
debug1: expecting SSH2_MSG_KEXDH_REPLY
debug3: check_host_in_hostfile: filename /home/bclifton/.ssh/known_hosts
debug3: check_host_in_hostfile: filename /etc/ssh/ssh_known_hosts
debug3: check_host_in_hostfile: filename /home/bclifton/.ssh/known_hosts
debug3: check_host_in_hostfile: filename /etc/ssh/ssh_known_hosts
debug2: no key of type 0 for host 111.111.111.111
debug3: check_host_in_hostfile: filename /home/bclifton/.ssh/known_hosts2
debug3: check_host_in_hostfile: filename /etc/ssh/ssh_known_hosts2
debug3: check_host_in_hostfile: filename /home/bclifton/.ssh/known_hosts
debug3: check_host_in_hostfile: filename /etc/ssh/ssh_known_hosts
debug2: no key of type 2 for host 111.111.111.111
The authenticity of host '111.111.111.111 (111.111.111.111)' can't be established.
RSA key fingerprint is 86:9a:f8:55:be:f6:2b:c2:75:2f:c7:2a:47:a6:f5:96.
Are you sure you want to continue connecting (yes/no)? yes
Warning: Permanently added '111.111.111.111' (RSA) to the list of known hosts.
debug2: bits set: 532/1024
debug1: ssh_rsa_verify: signature correct
debug2: kex_derive_keys
debug2: set_newkeys: mode 1
debug1: SSH2_MSG_NEWKEYS sent
debug1: expecting SSH2_MSG_NEWKEYS
debug2: set_newkeys: mode 0
debug1: SSH2_MSG_NEWKEYS received
debug1: SSH2_MSG_SERVICE_REQUEST sent
6f8c 24d9 bd86 51b5 8c43 7de9 85fe eb0d

Disconnecting: Bad packet length 1871455449.
debug1: Calling cleanup 0x8062cc0(0x0)

Answer : Problem: Unusual SSH Behavior - Disconnecting: Bad packet length on first connection.  Then it works.

Well, kind of an update. I don't know if a different installer was present or what, but one server did have FreeSSHd on it and it worked fine.  The add / remove programs lists the same version but the executable itself is different.  I copied this executable to all of the machines and SSH now works as expected.