This issue went away and then it came back, and now we finally seem to have found what was going on here.
There was a database query hanging which was being triggered from a regular job cleaning up users. It never got to finish because after half an hour it was being killed and restarted. When we performed that task manually the issue was gone.