Tente:
shutdown -r -f -m \hostname -c "Comment goes here"
Isso é um pouco drástico, mas eu tive a necessidade de fazer isso em um ambiente muito parecido com o que você descreve. Eu também abro uma janela de cmd e começo um ping -t contra o servidor para assistir quando a pilha de IP abaixa e volta para cima. Este é um indicador muito útil de atividade quando você não tem acesso físico ao servidor (ou está com preguiça de se levantar e ir até ele).
EDIT: (baseado no seu comentário) Ok, faça isso primeiro e tente novamente o acima (ou reinicie-o normalmente se isso funcionar). Veja isso que te leva mais longe. O -a abortará o desligamento do sistema.
shutdown -a -m \hostname