Assertion Occasionally Signed with Incorrect Cert

[Peter Schober]

* Mark Valites <mvalites at buffalo.edu> [2013-08-16 17:23]:
> There is a pretty clear error on the SP when it fails: "failed to
> decrypt assertion: Unable to resolve any key decryption keys." When
> it's thrown, the SP logs / SAML tracer show the assertion the SP is
> receiving has been signed with the old SP cert, which is still in
> the metadata (on both the IdP & SP).

The error is not about the signature and the IDP would not sign "with
the old SP cert". It means the IdP encrypted the assertion with a
public key that the SP has no private key for, i.e. the SP cannot
decrypt.  The signature would always be that of the issuer, which is
the IdP.
As such you'd find no configuration differences in any of your IdPs as
the SP's public key (wrapped in an X.509 certificate data structure)
comes in via SAML metadata.
Not that that explains anything, as your IdPs would then have to have
differing metadata configurations (which I suppose you said they
don't, as that would mean differing Shibboleth IDP configurations).
-peter