Nota de devolução Inter estadual/Posto Fiscal

Olá. Eu trabalho no setor de logística e tenho me deparado recentemente com pedidos de clientes de alguns estados sobre um tema até então desconhecido. Nota fiscal de devolução (parcial/total) no caso de avaria, precisa ser selada no posto fiscal? O que acontece - Essas avarias a transportadora não traz de volta por conta do custo elevado no retorno...onera ainda mais o frete, e nós cobramos dele que dão destino ao material. Emitimos/lançamos a nota de devolução do cliente e isso se registra nos livros fiscais..Porém, há clientes dizendo que isso não basta e que o Estado exige  o selo na nota. Em geral, são freteiros recontratados que nem saem da cidade...ainda mais do Estado. Alguém pode me orientar?