Você deve executar um ps aux para ver se algum dos scripts de desligamento foi interrompido, aguardando a conclusão de um processo. Deve ser algo como isto:
/etc/rc6.d/K##procname
Você pode tentar manualmente emitir um comando kill para esse script interrompido. Estranho, já que há um tempo limite definido nos scripts onde forçará um sinal -KILL para qualquer processo que tenha ficado.
Além disso, qual é o tempo de atividade do servidor / caixa? Eu experimentei um problema no passado em que uma caixa com um tempo de atividade de mais de um ano se recusa a encerrar. Nesse caso, eu matei cada processo manualmente, execute sync várias vezes para liberar todos os dados para o disco e forçar uma reinicialização (ciclo de energia).