This was revisited and the unsolicited block is being added to 3.1, which also includes the implementation of this check.

It's feasible, but no. The main purpose behind correlating them is to do so in a way that doesn't allow an attacker to hand his own response to somebody else to submit (it's an XSRF issue). A cookie has to be used, something the IdP doesn't see and the attacker can't necessarily get a victim to play to the SP. So it can't be something in the message.

Since unsolicted Responses are simply a kind of XSRF attack in their own right (just an intentional one), that's why you can't really implement the check safely without disabling that feature.

The SAML profile was written, incorrectly, to force people to support unsolicited SSO, and people use it heavily. So it's not a simple matter of just implementing that block. Half or more would just turn it off.

Woops, meant to say "to keep the outgoing AuthnRequest message ID along with the original request URL".

Would it be feasible to reuse RelayState storage to keep the outgoing AuthnRequest message ID along with the original request ID, provided of course that RelayState is enabled? The IdP is required by the spec to maintain the passed RelayState storage key, and afaik a new entry is created in the RS storage for every outgoing AuthnRequest.

I realize that it's unstructured plaintext storage and would require a hack-ish separator to store both the message ID and the initial request URL, but it's a technical possibility at least.

There's no point in validating it because the SP supports the MTI requirement of handling unsolicited responses. That would subvert anything that checking it would accomplish. The SP also doesn't maintain any request state, so there isn't any technical way to check it.

If in the future we decide to add a feature to block unsolicited responses, which would break a lot of actual usage, then it would be not only good, but necessary obviously, to do the check.