EnvelopedData the certificate is searched for in
CertificateStoreName.AddressBook certificate stores (based on
Is it possible that you do not have the certificate in any of those certificate stores?
Or is it possible that you have the certificate without key in one of those certificate stores?
If you post here your certificate finder implementation, we can spot some difference.