Parece que a versão init.d está começando com uma chave de servidor diferente que não é reconhecida, mas isso deve fornecer um aviso sobre o cliente. Pode ser o caso de o serviço estar lendo a configuração de algum outro local diferente do esperado. Também pode ser o caso de você ter um serviço xinetd em execução que rouba conexões de entrada para a porta 22.
tente iniciar o serviço com os métodos mencionados e procure uma diferença na saída de
ps aux | grep [s]shd
Isso pode lhe dar alguma pista sobre qual arquivo de configuração está sendo usado. Além disso, você pode querer verificar novamente se o sshd está escutando na porta 22 depois de iniciá-lo com /etc/init.d/sshd. Isso pode ser feito com
netstat -ntpl
Ou verificando se os logins "paswordfull" funcionam.