I guess you have checked this already and/or it will not be applicable to your scenario, but - we have experienced that here and there, never en masse as in your case. The reason here was always that the user's password had expired due to company_policy and had not been changed, so "physical" network_access to the directory where we store all our QV_apps was not available anymore.
What error does the end user sees when it starting to fail? Not what you see in the logs, but what error end-users sees in the process of opening the document. This is key because it could be, lack of CALs, Section Access or a true Qlik defect.
Now when you say " After about a week the failures reappeared." this still in SR5 or SR6? if still persist in SR5, it seems not to be a version problem, but something that changes, either in Qlikview and/or environment.
That looks more a Section access issue, does the document have section access? if they do, when end user start seeing the issue can you try to removed all section access and try again and see if the issue persist, or try to open a document that has NO section access.