Parece que conseguimos identificar o problema, não tem nada a ver com a mensagem de erro retornada pela prefeitura, possivelmente é algum bug interno com a série do documento, havíamos tentado enviar em uma série diferente, para manter as notas de testes separadas das de produção, e isso fazia com que as notas fossem sempre rejeitadas com a mensagem de erro citada acima, ao tentar emitir o mesmo documento na série 1, foi autorizado.
Muito obrigado pela ajuda, Arimateia! Estou deixando a explicação aqui para caso alguém tenha esse mesmo problema no futuro.