CTE com frete iniciado em outra UF

Prezados,

Estou com uma situação meio complexa, ao menos na minha opinião.

A empresa para qual minha transportadora presta serviços fez uma venda para um cliente de Teresina-PI, e este cliente emitiu uma nota de remessa para uma unidade sua em Curaça-BA, e solicitou que nosso CTE fosse emitido com base nesta nota, porem a operação ficou da seguinte forma.

O produto foi coletado em Fortaleza´CE e está aqui na Filial de Pacatuba-CE base da transportadora/revendedor.
O cliente emitiu a nota onde o endereço de oriegem é Teresina-PI, e destino Curaça-BA.

Dessa forma eu iria emitir um CTE com Origem Pacatuba-CE e destino Curaça-BA, e recolher a DIFAL normalmente pois o cliente não é contribuinte.

Mas meu setor fiscal me orientou a gerar o documento com origem Teresina-PI para recolher imposto para esta UF uma vez que o tomador do serviço é de lá.

Gerei o documento contra a minha logica, pois em meu entendimento os impostos devem ser gerados baseado na operação de transporte, uma vez que não houve coleta do produto em Teresina.

não se se fui claro nesta questão.

De fato, o ICMS é do Ceará pois as mercadorias foram retiradas do Ceará, o serviço de transporte iniciou no Ceará (art. 11, II, 'a', Lei Kandir):

"Art. 11. O local da operação ou da prestação, para os efeitos da cobrança do imposto e definição do estabelecimento responsável, é:
...
II - tratando-se de prestação de serviço de transporte:
a) onde tenha início a prestação;
...".

Obs. Não está claro como foi a coleta no Ceará (não foi dito se era um armazém geral, uma filial, etc. de forma que a emissão das notas fiscais fossem emitidas conforme o caso e DE FORMA CORRETA. Caso não tenha sido feito corretamente, poderia ter sido autuado acaso a fiscalização flagrasse o carregamento!
Seja como for, o ICMS de serviço é do Ceará, sem dúvidas!