An error occurred when validating an AS2 message

In an AS2 BizTalk solution for a client, we began to see a number of errors in the event log and the behaviour was that no messages or MDNs would arrive from a particular third party:

We checked the certificate store and determined the certificate had not been revoked or expired. Searching the certificate store for the certificate to see where it was installed revealed that the certificate was no longer in the Other People store which is used by BizTalk for verifying signed messages. We found the resolution on our own, but after the fact noticed the following MSDN article which seems to be pretty thorough about resolving this issue. Note that our resolution is the last item on the "User Action" list:

http://msdn.microsoft.com/en-us/library/bb898960%28BTS.10%29.aspx