Esta não é uma situação em que você deve projetar em torno das dependências circulares? Definir atrasos na inicialização do BIOS do servidor. Você tem vários servidores DNS, então é uma vantagem. Cache de DNS? Isso seria tão simples quanto usar endereços IP ou arquivos host para o seu NFS ou rede de armazenamento? Você não mencionou a tecnologia de virtualização específica, mas é possível definir a prioridade de inicialização da VM no VMWare, por exemplo ... Isso ocorre em vários servidores host?
Caso contrário, unidades de inicialização baseadas em SSD podem ajudar. Use uma distro com processos de inicialização do Upstart. Apare os daemons.