I did contact the QV support. Here is the response I got from them, in case someone else might encounter this problem in the future:
This is a bug in version 10, it has been reproduced but we have no fix for it yet.
Your recent support case as described below has now been confirmed by our Issue Analysis team as a bug, ID 37006 .
Due to uncertainties regarding potential related problems and program priorities we cannot guarantee a fix date at this time.
If the issue is critical to your business, please contact us for further discussions.
Please accept our sincere apologies for any inconvenience and let us know if you want us to close the case.
The problem fixed itself in yesterdays reload. The users were not in quarantine anymore so we could add the Document CALs normally to them again. In short: QlikTech doesn't have a fix for this issue in QV 10, but in QV 11, this issue is not known.
We plan to upgrade to QV 11 soon. Hopefully we won't encounter this bug again