Eu vi no documento Debian que se xorg.conf estiver faltando (que é o meu caso) o Xorg irá testar o seu hardware em cada inicialização. Então eu fiz um apt-get install firmware-linux-nonfree
(tenho o Debian estável) e instalei o xserver-xorg-video - ????? (placas de vídeo mais populares).
Depois de ter testado em algumas máquinas agora, esta parece ser a resposta, já que todos os testes foram bem sucedidos.