Isso pode soar bobo para você, mas você verificou todos os arquivos dpkg.log. *? Alguns serão gzipados, você pode utilizá-los usando zgrep ou rolá-los usando o zless.
Eu não sei ao certo, mas eu acho que às vezes você pode tropeçar em dependências estranhas, então talvez você tenha removido algum pacote que desencadeou a remoção de openssh-servers? Você fez alguma coisa com o dpkg, apt ou qualquer outra ferramenta que os utilizasse?
(Esta é uma "resposta" porque não posso comentar ainda. Não vejo por que eu precisaria de reputação para comentar, mas ...?)