What is the correct procedure to decrypt a xmldsig document encrypted
with the receiver's public key?
I can successfully load the correct private key from the .pfx file or
search for it in the certificate storage but I'm hit with the
"CryptographicException: Unable to retrieve the decryption key" in
Xml.EncryptedXml.DecryptDocument no matter what I do. Here is some of
the stuff I tried:

public static bool Decrypt(XmlDocument doc, X509Certificate2 cert)
{
       // Create a new EncryptedXml object.
       EncryptedXml exml = new EncryptedXml(doc);

       // I've tried to insert the certificate in certificate store
for decryption.
       X509Store store = new X509Store(StoreLocation.CurrentUser);
       store.Open(OpenFlags.ReadWrite);
       store.Add( cert);
       store.Close();

       // I've tried to add a key-name mapping.
       // This method can only decrypt documents that present the
specified key name.
       AsymmetricAlgorithm rsa = cert.PrivateKey;
       exml.AddKeyNameMapping("EncryptedData", rsa);    //the element
with encryption data
       exml.AddKeyNameMapping("Name-of-encrypted-element", rsa);    //
the name of encrypted element

       // Decrypt the element. or die trying
       exml.DecryptDocument();
}

The encrypted element has the following structure:
<EncryptedData xmlns="http://www.w3.org/2001/04/xmlenc#" Type="http://
www.w3.org/2001/04/xmlenc#Element">
    <EncryptionMethod Algorithm="http://www.w3.org/2001/04/
xmlenc#tripledes-cbc"/>
        <KeyInfo xmlns:ds="http://www.w3.org/2000/09/xmldsig#">
            <EncryptedKey Recipient="CAcert WoT User" xmlns:xenc="http://
www.w3.org/2001/04/xmlenc#">
                <EncryptionMethod Algorithm="http://www.w3.org/2001/04/
xmlenc#rsa-1_5"/>
                <CipherData>
                    <CipherValue>b64-encoded-data==</CipherValue>
                </CipherData>
            </EncryptedKey>
    </KeyInfo>
    <CipherData>
        <CipherValue>b64-encoded-data==</CipherValue>
    </CipherData>
</EncryptedData>

If encrypted data includes the X509 certificate as in following
structure, the decryption goes smoothly:
<EncryptedData Type="http://www.w3.org/2001/04/xmlenc#Element"
xmlns="http://www.w3.org/2001/04/xmlenc#">
    <EncryptionMethod Algorithm="http://www.w3.org/2001/04/xmlenc#aes256-
cbc" />
    <KeyInfo xmlns="http://www.w3.org/2000/09/xmldsig#">
            <EncryptedKey xmlns="http://www.w3.org/2001/04/xmlenc#">
                <EncryptionMethod Algorithm="http://www.w3.org/2001/04/
xmlenc#rsa-1_5" />
                <KeyInfo xmlns="http://www.w3.org/2000/09/xmldsig#">
                <X509Data>
                    <X509Certificate>b64-encoded-data==</X509Certificate>
                </X509Data>
            </KeyInfo>
            <CipherData>
                <CipherValue>b64-encoded-data==</CipherValue>
            </CipherData>
        </EncryptedKey>
    </KeyInfo>
    <CipherData>
        <CipherValue>b64-encoded-data==</CipherValue>
    </CipherData>
</EncryptedData>