Acho que posso ter encontrado. Eu adicionei uma dependência para o serviço dnscache ao serviço Hyper-V (vmms) via registro.
Funciona em 1 reinicialização. Vai esperar um par de dias antes de chamar isso de sucesso.
Atualizar
Funciona como um campeão. O tempo de inicialização é ainda muito mais rápido (eu acho que desde que a conectividade de inicialização do AD não está expirando).
Atualização 2
Começou a me dar o mesmo comportamento de vez em quando. Eu adicionei os outros dois serviços hyper-v (vhdsvc & nvspwmi) como dependências, e estou de volta aos trilhos novamente.
Atualização 3
Argh! Ainda esquisito. Acabei de adicionar uma dependência para um serviço para iniciar como "automático (atrasado)": wuauserv (Windows Update). Parece funcionar a partir de 3 dias.