Boa tarde Antonio,
para utilizar o serviço é necessário acrescentar o campo de Assinatura, neste caso de seu exemplo enviado está faltando o compo.
Segue um exemplo de como enviar um requerimento SOAP para o serviço de Consulta CNPJ.
<?xml version="1.0" encoding="UTF-8"?>
<soap12:Envelope xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns:xsd="http://www.w3.org/2001/XMLSchema" xmlns:soap12="http://www.w3.org/2003/05/soap-envelope">
<soap12:Body>
<ConsultaCNPJRequest xmlns="http://www.prefeitura.sp.gov.br/nfe">
<VersaoSchema>1</VersaoSchema>
<MensagemXML>
<![CDATA[<p1:PedidoConsultaCNPJ xmlns:p1="http://www.prefeitura.sp.gov.br/nfe" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"><Cabecalho Versao="1"><CPFCNPJRemetente><CNPJ>CNPJ</CNPJ></CPFCNPJRemetente></Cabecalho><CNPJContribuinte><CNPJ>CNPJ</CNPJ></CNPJContribuinte><Signature xmlns="http://www.w3.org/2000/09/xmldsig#"><SignedInfo><CanonicalizationMethod Algorithm="http://www.w3.org/TR/2001/REC-xml-c14n-20010315"/><SignatureMethod Algorithm="http://www.w3.org/2000/09/xmldsig#rsa-sha1"/><Reference URI=""><Transforms><Transform Algorithm="http://www.w3.org/2000/09/xmldsig#enveloped-signature"/><Transform Algorithm="http://www.w3.org/TR/2001/REC-xml-c14n-20010315"/></Transforms><DigestMethod Algorithm="http://www.w3.org/2000/09/xmldsig#sha1"/><DigestValue>YFEFXgrm2wO8LOTYK5L2Job8tss=</DigestValue></Reference></SignedInfo><SignatureValue>ASSINATURA EM BASE64</SignatureValue><KeyInfo><X509Data><X509Certificate>CERTIFICADO EM BASE64</X509Certificate></X509Data></KeyInfo></Signature></p1:PedidoConsultaCNPJ>]]></MensagemXML>
</ConsultaCNPJRequest>
</soap12:Body>
</soap12:Envelope>
Confira também o manual do WebService no site do Nota do Milhão da Prefeitura de São Paulo.
Os items das tabelas descrevem os campos e também os XML's de exemplo
http://nfpaulistana.prefeitura.sp.gov.br/arquivos/exemplosv02.zip
Obs: sempre devem conter a assinatura no padrão como enviado acima.
http://notadomilhao.prefeitura.sp.gov.br/cidadao/informacoes-gerais/manuais-arquivos/nfe_web_service.pdf/view