What makes you think it might be something to do with the distributed session store?
Please enable SAML trace and send the generated log file as an email attachment to support@componentSpace.com mentioning your forum post.
Also, are you able to reproduce the issue in a simple test app?
If so, please zip up the source code and project and include this so we can attempt to reproduce the problem here.
There must be something a little different about the app or the environment in which it runs to cause such a fundamental problem.
Any ideas what might be different about this app or the environment?
Thanks.