My best guess would be that there is an outdated jar file in your userlib folder. Could that be the case?
If so you may want to update all marketplace modules in your app and clean up any old jars that are no longer needed. A good way to test this: delete everything from the userlib folder and then download latest versions of all marketplace modules and see if that fixes the problem. This may give you pointers into what jar files needs removing/updating. You can always do a rollback of your changes if it doesn't fix the problem.
If you don't rollback, be sure to do a proper regression test after this.
I contacted the Mendix support team, where they confirmed that this is a bug specific to version 3.3.1 and specific when setting up SP without encryption. After I downgraded to SAML version 3.2.5, set the configuration data – everything worked great. We expect this bug to be fixed in the new version.