We've finally managed to trigger the problem with increased logging. The relevant part of the stacktrace is:
[2014-04-29 20:01:09,946] [DEBUG] [ajp-bio-8009-exec-38] Servlet | Catching
java.lang.IllegalStateException: getAttribute: Session already invalidated
Other logging shows that 2 requests were sharing the same httpsession, even though these requests are WS-requests, which do not use bound sessions. At the moment we can only conclude it is caused by this race condition in the old version of Tomcat: https://issues.apache.org/bugzilla/show_bug.cgi?id=55521 . We've instructed our administrators to update Tomcat, which they did not find necessary before, even though the outdated version is remotely exploitable and vulnerable to several DOS-attacks. I'll report back when I have confirmation that this issue is indeed solved by upgrading Tomcat (which can take some time, because it is only triggered once every few days).