Nota Fiscal de veiculação de anúncio

Amigos, bom dia

Tenho como cliente uma Editora de Jornais, Revistas e Livros localizada na cidade de São Paulo, que pratica a maior parte de sua receita como VEICULAÇÃO DE ANÚNCIO e emite Nota Fatura para cobrança de seus serviços.
Meu questionamento é sobre a emissão de Nota Fiscal Modelo 21 (Estadual), já que estes serviços não podem ser cobrados mediante nota fiscal de serviços (Município).
Procurei em vários sites e regulamentações e não consegui encontrar nada que me diga, com toda certeza, de que a empresa necessita emitir a Modelo 21.
O que ocorre é que alguns clientes de fora do Estado de São Paulo não estão aceitando mais a Nota Fatura, alegando que a empresa estaria obrigada a emitir Nota Fiscal Estadual (modelo 21) para a cobrança e simplesmente estão deixando de pagar os serviços contratados.
O CNAE principal da empresa e 58.22-1-01 - Edição integrada à impressão de jornais diários.

Será que vocês conseguem me auxiliar nisto?

Muito obrigado e abraços!

Jorge Correa

Nota fiscal modelo 21, sem dúvidas!
Regras gerais ver o Convênio ICMS 115/2003.
No Estado do Ceará tal matéria está regulamentada no Decreto 27492/2004.
Acredito que a legislação de São Paulo tenha uma seção tratando do assunto.

O conceito de telecomunicação está no artigo 61, §1º, Lei Federal nº 9.472/97:
Art. 60. Serviço de telecomunicações é o conjunto de atividades que possibilita a oferta de telecomunicação.
§ 1° Telecomunicação é a transmissão, emissão ou recepção, por fio, radioeletricidade, meios ópticos ou qualquer outro processo eletromagnético, de símbolos, caracteres, sinais, escritos, imagens, sons ou informações de qualquer natureza.
Em essência não existe diferença entre comunicação e telecomunicação, os termos divergem por causa da forma como ocorre a comunicação. O prefixo “Tele” indica que a comunicação ocorre à distância, via fio, meios ópticos, radioeletricidades, etc. como ensina a norma acima.
Dito isso, a Nota Fiscal de Serviço de Telecomunicação (Modelo 22) serve para serviço de comunicação que seja via telefone (fixa ou móvel). O próprio Modelo 22 já traz no leiaute o campo para indicar o número do telefone chamado.
Por sua vez, a Nota Fiscal de Serviço de Comunicação (Modelo 21) serve para os demais serviços, por exemplo, publicidade em revistas, propagandas comerciais, TV por assinatura, etc. Oportuno dizer que no corpo da nota fiscal modelo 21 existe o campo para discriminação do serviço prestado, diferentemente do Modelo 22 que pede a discriminação do número do telefone chamado.