Yeah, I didn't even mention the other bindings (HTTP-Redirect, Artifact, etc.) because they're not widely supported. Only SAML's HTTP-POST binding enjoys "every IDP supports this exact protocol" status.

FWIW, the for library I work on -- github.com/ssoready/ssoready -- we sidestepped this issue by simply not using SAML RelayState at all under the hood. Between the fact that it's vulnerable to attacker manipulation, and the size limits, it's not worth the pain. We just implement SAML RelayState / OAuth `state` via good old database persistence.