Existe algum outro binário sshd na caixa configurada sem o GSS e o PAM, talvez?
Tente isto:
/usr/sbin/sshd -d -f /etc/ssh/sshd_config
e veja se você recebe os mesmos erros acima. Se não, seu service sshd start
executará um binário diferente. Nesse caso, você pode tentar:
/bin/bash -x /etc/init.d/sshd start
e percorra a saída (pode ser bastante longa) para descobrir qual sshd
binário está sendo executado.