Sorry for such long delay in response but it seems it got stuck in our engineering department.
They found 2 possible cases to why this is failing.
Case 1: HTTP Redirect binding (GET /samlp/client )
They investigated a bit further and found the source of the problem. According to SAML specification, when using HTTP Redirect binding (like in this situation) the SAML Request (xml) is built with these steps:
DEFLATED => base64 => url encoded => set to SAMLRequest parameter
(See section “22.214.171.124 DEFLATE Encoding“ on https://docs.oasis-open.org/security/saml/v2.0/saml-bindings-2.0-os.pdf ).
It seems the case we have here is caused because the SAML Request was not url encoded before sending it to Auth0. That creates a problem: + character is transformed to (whitespace), that makes the request parsing fail.
Solution: Ask the Identity Provider that created the request to url encode the SAMLRequest.
Case 2: HTTP POST binding (POST /samlp/client )
They also found that the Request itself, once parsed, contains POST binding. When POST binding is used the caller does not need to url-encode the base64 data, that would explain why it is not url-encoded.
Solution: Ask the Identity Provider to send the request using POST binding.