Devolução Interestadual Efetuada por não Contribuinte - Documento para acompanhar o trânsito

Prezados,
Muito boa tarde!
Qual é o documento próprio para trânsito de mercadoria devolvida em operação interestadual, quando o remetente é um órgão público ou mesmo empresa privada não contribuinte de ICMS?
As transportadoras recusam o serviço de transporte se a mercadoria não estiver acompanhada de nota fiscal. Ocorre que alguns estados não permitem emissão de NFe avulsa por não contribuinte. Quanto aos órgãos públicos, todos alegam que não são obrigados a emitir nota. E nós destinatários, ficamos sem saber como proceder.
Acredito que todas as empresas que realizam operações interestaduais com destinatário não contribuinte passam essa mesma dificuldade.
Exemplo: Venda do RJ para PR destinatário não contribuinte. O destinatário precisa devolver a mercadoria. Não emite NFe e o estado não permite que não contribuinte emita NFAe. A transportadora alega que sem nota fiscal, não pode transitar.
Qual é a orientação nesse caso?

Boa tarde!

Neste caso você emite a NFe de devolução dando entrada na mercadoria, inclusive é a única maneira de registrar a devolução e não pagar imposto indevidamente.

Por exemplo: você emite a NFe com CFOP 2202 deixa o Tipo da NF como "0" Entrada e referenciando sua NF de venda.