I believe we fixed it for good now.
Not seeing any invalid session messages pop up anymore (at least in our logs, there will be a few who get one or two for the next 5min, but should resolve itself afterwards)
What happened:
One of our servers had a PSU fail (which was replaced earlier today [~5hrs ago]), however due to the way we manage our auth system, none of us realized that it had even died. (Win yes?)
With that said, it had reset a few things, which showed us some bugs in our auth implementation. They've been fixed, so this type of failure shouldn't happen again in the future.
If you're still having issues, please, let us know.