Vitor,
A LC 116/2003 diz o seguinte sobre local de serviço prestados e as retenções:
Art. 4o Considera-se estabelecimento prestador o local onde o contribuinte desenvolva a atividade de prestar serviços, de modo permanente ou temporário, e que configure unidade econômica ou profissional, sendo irrelevantes para caracterizá-lo as denominações de sede, filial, agência, posto de atendimento, sucursal, escritório de representação ou contato ou quaisquer outras que venham a ser utilizadas.
Art. 6o Os Municípios e o Distrito Federal, mediante lei, poderão atribuir de modo expresso a responsabilidade pelo crédito tributário a terceira pessoa, vinculada ao fato gerador da respectiva obrigação, excluindo a responsabilidade do contribuinte ou atribuindo-a a este em caráter supletivo do cumprimento total ou parcial da referida obrigação, inclusive no que se refere à multa e aos acréscimos legais.
§ 2o Sem prejuízo do disposto no caput e no § 1o deste artigo, são responsáveis: (Vide Lei Complementar nº 123, de 2006).
I – o tomador ou intermediário de serviço proveniente do exterior do País ou cuja prestação se tenha iniciado no exterior do País;
II – a pessoa jurídica, ainda que imune ou isenta, tomadora ou intermediária dos serviços descritos nos subitens 3.05, 7.02, 7.04, 7.05, 7.09, 7.10, 7.12, 7.14, 7.15, 7.16, 7.17, 7.19, 11.02, 17.05 e 17.10 da lista anexa.
Meu entendimento é que o serviço é devido para Curitiba pelo prestador do serviço, pois os serviços retidos estão no Art. 6º § 2º.
Porém SP tem uma Lei que o prestador de serviço de outro município deverá ser cadastrado no CPOM:
www.prefeitura.sp.gov.br
1) Quem deve se inscrever no cadastro?
Quem atender, concomitantemente, às seguintes condições:
a) ser prestador de serviços;
b) estar constituído na forma de pessoa jurídica;
c) estar estabelecido fora do Município de São Paulo;
d) prestar, para contratante estabelecido no Município de São Paulo, qualquer serviço descrito no art. 69 do Decreto 53.151/2012;
e) emitir nota fiscal ou outro documento fiscal equivalente autorizado por outro Município.
Consulte, também, a pergunta nº 2.
Creio que seja a falta deste cadastro que esta gerando a dúvida do tomador de serviço.
Caso não for o CPOM sugior que entre em contato com a prefeitura de Curitiba, pois como sabemos nem todos os municípios seguem a LC 116/03 gerando duvidas para os contribuintes.
Att,
Fabrício Octaviani