It turns out that the clou of the solution was in this little piece: security.oauth20.token.limit.error. The users were running into a limit.
The OAuth token limit is set in the <DMGR profile path>/config/cells/<yourCell>/oauth20/connectionsProvider.xml file:

<!-- optional limit for the number of tokens a user/client/provider combination can be issued -->
<parameter name="oauth20.token.userClientTokenLimit" type="ws" customizable="true">
    <value>250</value>
</parameter>

The default value is ‘250’. The recommended value is ‘500’. You can see if your users were indeed running into this limit by running the following SQL query (query based on MS SQL server, but pretty similar in DB2 or Oracle):

Extending OAuth Cache count to 500