Rodrigo,
De acordo com o art. 3° da Lei complementar 116/2003, o ISS é devido no local do estabelecimento prestador, ou seja, onde está estabelecida a empresa prestadora de serviços. Porém, em alguns municípos é exigido um cadastro de empresas de outras cidades para que estas não tenham o ISS retido. São Paulo é uma dessas cidades.
Verifique se o CNPJ da empresa de Belo Horizonte está cadastrado no CPOM (Consulta prestador de serviços), e, caso esteja, o ISS não será retido e deverá ser recolhido somente para o município de BH. Caso contrário (não havendo cadastro) o ISS será retido pelo tomador ao município de São Paulo e a empresa de BH não poderá deixar de pagá-lo para seu município.
Importante lembar que o ISS somente será retido se o serviço for um daqueles constantes da lista do anexo único do decreto 46.598/2005.
Sugiro que dê uma olhada no site que segue (Legislação CPOM-SP) para completo entendimento sobre essa legislação e já informo que outros municípios como Rio de Janeiro e Porto Alegre possuem legislações semelhantes.
O cadastro é simples e impede a retençaõ do ISS sobre seu serviço, mas deverá ser informado todos os serviços prestados por sua empresa, para que não haja dúvida do tomador de serviços e recolhimento indevido.
Espero ter ajudado.