Recently I found myself trying to talk to a webservice using signing. It was a WCF calling a Java webservice using a certificate to sign messages. I kept getting the following exception message:

The incoming message was signed with a token which was different from what used to encrypt the body. This was not expected.

After a wild goose chase we finally figured out that the certificate was corrupted. Just installing the certificate again solved the issue.