Tu es sûr que le sshd que tu as réinstallé "à la main" est le bon ?
Qu'il est démarré par les scripts d'init ?

Sinon tu peux compléter lesdits scripts par quelques echo dans un fichier pour analyser la question après le boot...