Francisco,
Pelo que descobri através de pesquisa a legislação pertinente, a referida retenção é devida tratando-se de empresas de fora do município. Veja o que diz o Decreto 50.500/09, que consolida a legislação tributária do município de São Paulo:
"Art. 148. O prestador de serviços que emitir nota fiscal ou outro documento fiscal equivalente autorizado por outro Município ou pelo Distrito Federal, para tomador estabelecido no Município de São Paulo, referente aos serviços descritos nos itens 1, 2, 3 (exceto o subitem 3.04), 4 a 6, 8 a 10, 13 a 15, 17 (exceto os subitens 17.05 e 17.09), 18, 19 e 21 a 40, bem como nos subitens 7.01, 7.03, 7.06, 7.07, 7.08, 7.13, 7.18, 7.19, 7.20, 11.03 e 12.13, todos constantes da lista do caput do artigo 137, fica obrigado a proceder à sua inscrição em cadastro da Secretaria Municipal de Finanças, conforme dispuser o regulamento.
...
§ 2º. As pessoas jurídicas estabelecidas no Município de São Paulo, ainda que imunes ou isentas, são responsáveis pelo pagamento do Imposto sobre Serviços de Qualquer Natureza - ISS, devendo reter na fonte o seu valor, quando tomarem ou intermediarem os serviços a que se refere o caput deste artigo executados por prestadores de serviços não inscritos em cadastro da Secretaria Municipal de Finanças e que emitirem nota fiscal autorizada por outro Município" (grifos meus)
O item 4 refere-se aos serviços de saúde, assistência médica e congêneres.
Resta ver se a mesma retenção aplica-se mesmo quando ambas as empresas estão estabelecidas na cidade de São Paulo.
[...]