Odeio informar que resolvemos o problema removendo o cabo HDMI, desligando totalmente os computadores (estávamos apenas "reiniciando" antes) e substituindo o cabo HDMI depois de inicializado e conectado.
Agora podemos reiniciar sem remover o cabo e ele funciona bem.