SAML Signature verification failed

Our IdP is a Salesforce.com org. The SP is a third party .Net application. During development, the 3rd party reported that they're unable to validate the SAML response sent.

We decided to try validating on our end using ComponentSpace to validate the SAML response. Below is what we tried:

// Load the certificate from the file: certInFile
// Load the SAML in an XMLElement: samlXml
// Retrieve the certificate from the SAML: certInSaml

Console.WriteLine("SAML is valid ? " + SAMLResponse.IsValid(samlXml));
Console.WriteLine("Is SAML signed? " + SAMLMessageSignature.IsSigned(samlXml));
Console.WriteLine("Certificate found in SAML is same as certificate file? " + certInFile.Equals(certInSaml));
Console.WriteLine("Validated SAML with certificate found in SAML" + SAMLMessageSignature.Verify(samlXml, certInSaml));
Console.WriteLine("Validated SAML with certificate file" + SAMLMessageSignature.Verify(samlXml, certInFile));

I'm getting true for everything above, except the last two. So:

1. The SAML is valid
2. The SAML has a valid signature
3. The public key certificate in the SAML is the same as the certificate file we have
4. The SAML is signed with the private key of neither the certificate file nor the public key sent in the SAML

From 3,4 can we conclude that Salesforce is signing but with a different certificate but sending the wrong public key in the response?!

Edit: Sample SAML is here http://pastebin.com/J8FTxnhJ

What am I missing?

This worked when we didn't decode the base64 encoded SAML generated but directly tried to validate it. However, still not sure why the ComponentSpace methods reported differently for the decoded string.