No meu caso, estava assim:
<infANTT>
<RNTRC>50088933</RNTRC>
<infContratante>
<CNPJ>00000000000000</CNPJ>
</infContratante>
</infANTT>
<veicTracao>
<placa>GWW5669</placa>
<tara>7200</tara>
<capKG>5100</capKG>
<prop>
<CNPJ>88888888000100</CNPJ>
<RNTRC>50088933</RNTRC>
<xNome>RAZAO SOCIAL DO PROPRIETARIO DO VEICULO LTDA</xNome>
<IE>0</IE>
<UF>PR</UF>
<tpProp>0</tpProp>
</prop>
<condutor>
<xNome>NOME DO MOTORISTA</xNome>
<CPF>11111111111</CPF>
</condutor>
<tpRod>02</tpRod>
<tpCar>02</tpCar>
<UF>PR</UF>
</veicTracao>
PS: Retirei o número dos documentos e razão social dos envolvidos para preservar os dados em pesquisas no google.
Vamos lá: O Veículo não é de propriedade da empresa emitente do MDFe, porém, esta registrado na ANTT junto a empresa emitente. Neste caso, o que eu sempre fiz foi: Nos campos RNTRC informar o registro da EMITENTE, pois o veículo esta vinculado a ela.
Neste caso, gera o erro.
Para autorizar e seguir viajem, o cliente alterou o cadastro do veículo e no campo CNPJ do proprietário, informou o seu próprio CNPJ, assim o MDFe foi autorizado.
Creio que este caso específico seja um bug no sistema de validação da sefaz, pois a consulta na ANTT retorna positivo para a operação.