When trying to implement certificate backed managed InfoCards you might run into this slightly misleading error message:

“There was a failure making a WS-Trust exchange with an external application. Could not retrieve token from identity provider.

Inner Exception: SOAP security negotiation failed. See inner exception for more details.
Inner Exception: The certificate ‘CN=xy’ must have a private key. The process must have access rights for the private key.”

The real cause for this error is a bug in Windows CardSpace. You can workaround that by disabling service credential negotiation on your STS binding by setting negotiateServiceCredential to false.

Thanks to the Zermatt forum people for pointing me into the right direction!