Existem vários truques que você pode fazer nesta situação para diagnosticar o problema e acelerar a reinicialização, na ausência de uma placa de Gerenciamento Remoto.
Você pode tentar gerenciar remotamente o servidor com suas ferramentas de gerenciamento locais. Por exemplo, você pode executar o services.msc e conectar-se ao computador remoto para inspecionar os serviços em execução. Você poderia executar o eventvwr e conectar-se ao computador remoto para examinar os logs de eventos atuais (talvez um serviço tenha sido interrompido durante a tentativa de reinicialização?)
Você pode tentar usar a ferramenta SysInternals "PSExec" para se conectar ao sistema, e matar processos manualmente ou anular a reinicialização atual e reemitir o comando de desligamento.
Eu tive um problema semelhante com um cluster do Hyper-V R2 SP1 em que um dos hosts do Hyper-V levava regularmente cerca de duas horas para ser reinicializado. As sessões do RDP cairiam, mas o host ficaria preso em "Encerrando o serviço de cluster". No meu caso, fui capaz de corrigir o problema, matando remotamente o serviço de cluster com o seguinte comando:
taskkill / S Hyper-V-Host / clussvce.exe IM
O servidor será reinicializado instantaneamente.