Fora as situações aqui já documentadas, tivemos outra situação onde nenhuma das soluções propostas resolveu.
Chegamos a suspeitar do certificado também e testamos acessando:
https://cav.receita.fazenda.gov.br/autenticacao/login
Mas, aceitou o certificado A3 normalmente. Então, desconsideramos essa hipótese.
Assim a suspeita caiu sobre os dados, pois era uma NFe digitada.
Como havia uma NFe igual (no mês anterior) que havia sido emitida sem problema, foi excluido a nota em digitação e feito uma importação daquela do mês anterior.
Finalizou-se e deu tudo certo. Ficamos sem saber qual campo estava gerando o problema.