Acabou sendo um problema de driver em relação aos sistemas operacionais. Não tínhamos drivers de 64 bits para alguns dos sistemas operacionais mais recentes que foram entregues no servidor de gerenciamento de impressão. Quando chegamos lá, as impressoras começaram a aparecer sem problemas.
Que resposta simples - eu estava me chutando: -P