We found the answer. We looked into our web logs. It showed that we were receiving some weird http actions (verbs/methods) like OPTIONS, PROPFIND and HEAD.
This seems to the cause of some of theses exceptions. This explains why it was intermittent.
We reproduced the issue with the curl.exe tool:
curl.exe -X OPTIONS http://localhost/v2.3.1.0/(S(boztz1aquhzurevtjwllzr45))/Form/Fill/273
curl.exe -X PROPFIND http://localhost/v2.3.1.0/(S(boztz1aquhzurevtjwllzr45))/Form/Fill/273
curl.exe -X HEAD http://localhost/v2.3.1.0/(S(boztz1aquhzurevtjwllzr45))/Form/Fill/273
The fix we used was to add an authorization section to web.config:
<authorization>
<deny users="*" verbs="OPTIONS, PROPFIND, HEAD"/>
</authorization>