Depois de muita dor de cabeça, cedemos e tivemos a impressora da empresa. Eles fizeram uma reinicialização total do hardware (redefinir todas as configurações) e atualizaram o firmware da impressora para o mais recente disponível.
Uma vez que a reconfiguramos para a nossa rede e eu reinstalei os drivers da impressora em todos os computadores (já que eu havia feito tanto mexer e brincar com as configurações), ela começou a imprimir rapidamente novamente.