I've also spent a lot of time trying to figuring this one out, so in case anyone reads this, this might help.

Following the tutorial here: ttp://www.sharepoint-insight.com/2016/03/21/step-by-step-sharepoint-online-authentiaction-process-via-http-protocol/ the SAML message has to be wrapped in a SOAP message and then has to be sent to https://login.microsoftonline.com/RST2.srf as in step 10. There is also an example of how the full token shall look like.

This endpoint also gave me more useful error messages like "MinorVersion missing". However, I could not get this to work as my token was SAML 2.0 and the endpoint at the end gave me the message that it only understands 1.1.