UFA !
Finalmente, depois de uma semana batendo cabeça, parece que descobri o motivo.
Ocorre que até então eu só tinha testado no ambiente de homologação, em momento nenhum testei em ambiente de produção... e sempre dava o mesmo erro.
Aí agora tive a idéia de mudar pra produção, enviei a nota e... passou !
Ao que parece o ambiente de homologação, por algum motivo, não está funcionando para meu cliente, talvez porque precise de alguma autorização lá na prefeitura, sei lá... Mas no ambiente de produção está indo. O ruim é que não tenho como testar nada, agora é arrumar com o avião voando !
Obrigado a todos pela ajuda !