Session problem: Login cookie validation hash mismatch! Cookies have been tampered with

We have trouble with login/cookie/session in XWiki:

• Login into XWiki (LDAP)
• Leave browser window untouched for 30 minutes (tomcat session duration)
• Load a page
• Message "You do not have permission to view the document or to perform that action." appears
• Logout / login
• Message keeps showing up
• Logout / close browser window
• New browser window / Login
• Login works
  • Login works only if no deep link in the wiki is used

This appears consistently across all user in our LAN.‚