Ananias,
A empresa tomadora do serviço realmente pagou as guias de ISSQN?
A empresa prestou serviço no município A e na NF que é emitida pelo município B, foi informado que o serviço foi efetuado no município A correto?
O tomador de serviço recolheu o ISS para o município A ou B?
Se foi recolhido para o município A, a prefeitura da sede no caso município B não tem que cobrar valor algum da empresa prestadora, pois a LC 116/03 diz que o ISS é retido e devido no município da prestação de serviço.
Agora se o ISS foi retido e pago para o município B, o tomador do serviço deverá solicitar a devolução dos valores pagos e fazer o recolhimento no município A.
olha o que fala a lei do ISS para serviços da construção civil:
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.
§ 1o Os responsáveis a que se refere este artigo estão obrigados ao recolhimento integral do imposto devido, multa e acréscimos legais, independentemente de ter sido efetuada sua retenção na fonte.
§ 2o Sem prejuízo do disposto no caput e no § 1o deste artigo, são responsáveis: (Vide Lei Complementar nº 123, de 2006).
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.
Sendo assim entendo que por não ter ocorrido o pagamento no município A, ele poderá sim cobrar da empresa tomadora o recolhimento.