Bom Dia.
A retenção de ISS deverá ser efetuada e recolhida para o município de Curitiba, onde os serviços estão sendo desenvolvidos de fato. O fato do prestador emitir a NF contra empresa tomadora estabelecida em SP não interfere. Este serviços é devido no local da prestação, ou seja, onde a limpeza está sendo efetivamente desenvolvida ( LC 116/2003 Art. 3 ). Vale frisar que o prestador deverá informar na Nota Fiscal, no ato da emissão, a alíquota de ISS que ele pagou no DAS do mês imediatamente anterior. Caso não informe, o tomador obrigatoriamente deverá efetuar a retenção de ISS pela alíquota máxima (5%).
Quanto a retenção de INSS a Instrução normativa 971, em seu artigo 191 determina o seguinte:
Art. 191. As ME e EPP optantes pelo Simples Nacional que prestarem serviços mediante cessão de mão-de-obra ou empreitada não estão sujeitas à retenção referida no art. 31 da Lei nº 8.212, de 1991, sobre o valor bruto da nota fiscal, da fatura ou do recibo de prestação de serviços emitidos, excetuada:
I - a ME ou a EPP tributada na forma dos Anexos IV e V da Lei Complementar nº 123, de 2006, para os fatos geradores ocorridos até 31 de dezembro de 2008; e
II - a ME ou a EPP tributada na forma do Anexo IV da Lei Complementar nº 123, de 2006, para os fatos geradores ocorridos a partir de 1º de janeiro de 2009.
§ 1º A aplicação dos incisos I e II do caput se restringe às atividades elencadas nos §§ 2º e 3º do art. 219 do RPS, e, no que couberem, às disposições do Capítulo VIII do Título II desta Instrução Normativa.
§ 2º A ME ou a EPP que exerça atividades tributadas na forma do Anexo III, até 31 de dezembro de 2008, e tributadas na forma dos Anexos III e V, a partir de 1º de janeiro de 2009, todos da Lei Complementar nº 123, de 2006, estará sujeita à exclusão do Simples Nacional na hipótese de prestação de serviços mediante cessão ou locação de mão-de-obra, em face do disposto no inciso XII do art. 17 e no § 5º-H do art. 18 da referida Lei Complementar.
Observe que o que determina a Lei complementar 123/2006, em seu Artigo 18 - §5º-C
§ 5º-C. Sem prejuízo do disposto no § 1º do art. 17 desta Lei Complementar, as atividades de prestação de serviços seguintes serão tributadas na forma do Anexo IV desta Lei Complementar, hipótese em que não estará incluída no Simples Nacional a contribuição prevista no inciso VI do caput do art. 13 desta Lei Complementar, devendo ela ser recolhida segundo a legislação prevista para os demais contribuintes ou responsáveis:
I - construção de imóveis e obras de engenharia em geral, inclusive sob a forma de subempreitada, execução de projetos e serviços de paisagismo, bem como decoração de interiores;
II - (REVOGADO);
III - (REVOGADO);
IV - (REVOGADO);
V - (REVOGADO);
VI - serviço de vigilância,limpeza ou conservação.
Espero ter ajudado.