Não importa quais alterações eu faça, o cancelamento simplesmente nunca está no formato correto. Já li várias vezes o manual e não consigo encontrar onde possa estar o erro. Segue o XML usado (capturado com a ferramenta Fiddler).
<s:Envelope xmlns:s="http://schemas.xmlsoap.org/soap/envelope/">
<s:Body>
<CancelarNfse xmlns="http://homologacao.issfortaleza.com.br">
<CancelarNfseEnvio xmlns=""><?xml version="1.0" encoding="utf-8"?>
<CancelarNfseEnvio xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns:xsd="http://www.w3.org/2001/XMLSchema" xmlns="http://www.ginfes.com.br/servico_cancelar_nfse_envio_v03.xsd">
<Pedido xmlns="">
<InfPedidoCancelamento Id="132" xmlns="http://www.ginfes.com.br/tipos_v03.xsd">
<IdentificacaoNfse>
<Numero>201412345678901</Numero>
<Cnpj>07118890000180</Cnpj>
<InscricaoMunicipal>194666</InscricaoMunicipal>
<CodigoMunicipio>2304400</CodigoMunicipio>
</IdentificacaoNfse>
<CodigoCancelamento>2304</CodigoCancelamento>
</InfPedidoCancelamento>
</Pedido>
<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="#132">
<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>[..]</DigestValue>
</Reference>
</SignedInfo>
<SignatureValue>[..]</SignatureValue>
<KeyInfo>
<X509Data>[..]</X509Certificate>
</X509Data>
</KeyInfo>
</Signature>
</CancelarNfseEnvio>
</CancelarNfseEnvio>
</CancelarNfse>
</s:Body>
</s:Envelope>
Pelas pesquisas que fiz, vi algumas pessoas comentando que o formato no manual é diferente do que deve ser realmente enviado, mas não consegui uma informação realmente conclusiva sobre isso.
Agradeço aos que puderem ajudar.