Boa tarde, Rodrigo,
Sobre essa situação específica, o que aconteceu foi um erro no preenchimento da nota fiscal de serviços, em que o campo do tomador não foi identificado corretamente no momento da emissão, ainda que os valores retidos tenham sido recolhidos dentro do prazo. Nesse caso a resposta é tranquilizadora: não é necessário pagar os impostos novamente, pois o recolhimento já feito continua válido, já que ele está vinculado ao fato gerador da prestação do serviço e não propriamente ao preenchimento correto de todos os campos cadastrais do documento fiscal.
O procedimento correto aqui depende da regra do município onde a nota foi emitida, já que a emissão de NFS-e e as regras de substituição ou cancelamento de documentos fiscais de serviço são de competência municipal, sem uma regra nacional única. Em geral, a maioria dos municípios permite a substituição da nota fiscal quando há erro em campos como o tomador do serviço, sem que isso implique em novo recolhimento, desde que o erro seja de natureza cadastral e não altere a base de cálculo, a alíquota ou o valor do imposto devido. Essa substituição normalmente é feita dentro de um prazo estabelecido pela prefeitura, que pode variar de trinta a noventa dias contados da emissão original, e alguns sistemas municipais fazem isso por meio de carta de correção eletrônica quando o erro é considerado simples, enquanto outros exigem o cancelamento da nota e emissão de uma nova com o tomador correto, vinculando o documento novo ao recolhimento já realizado.
Diante disso, o caminho mais seguro é acessar o portal da nota fiscal eletrônica de serviços do município em questão, ou o sistema nfse.gov.br quando o município já estiver integrado ao padrão nacional, e verificar se existe a opção de substituição de NFS-e com o motivo erro de tomador, informando o número da nota original e do pagamento já efetuado. Se o sistema municipal permitir apenas cancelamento, é importante verificar se esse cancelamento pode ser feito fora do prazo padrão quando há erro comprovado de tomador, apresentando a justificativa e o comprovante do recolhimento original para que ele seja aproveitado na nota substituta.
Também é recomendável guardar a comprovação de que o serviço foi efetivamente prestado ao tomador correto, como contrato, ordem de serviço ou troca de e-mails, para o caso de a prefeitura solicitar comprovação adicional do vínculo entre a nota substituta e o pagamento original, já que o tomador é uma informação central para fins de fiscalização cruzada entre prestador e tomador, especialmente em municípios que cruzam essas informações com a retenção de ISS declarada pelo tomador.