Acho que descobri o culpado e não tem nada a ver com a própria VM. Acho que nossas configurações de rede / firewall mudaram recentemente e estavam interferindo no tráfego SSH. Conectei-me à VM com uma conexão de internet diferente (fora de nossa rede corporativa) e consegui administrar a máquina pelo SSH sem problemas.
Deixarei isso como a resposta aceita no caso de alguém aparecer junto com SSH estranho aleatório e isso for útil, mas os mods devem se sentir à vontade para fechar essa questão se ela for muito pequena.