Many new adobe instals relate to a single root cause, that they never properly debugged before product release -- and being adobe, they are reticent to admit problem or post a fix.  Yours may not be caused by this, but you should try it on at least one system that is giving the problem.

1.  Remove ALL adobe software from the system -- the InDesign first, as it is the newest, but you also have to remove acrobat and any other relict adobe applications as well.  Reboot -- now set a restore point, and open regedit,  then F3 search the registry for "Adobe" without the quotes.  All paths to Adobe products can be deleted, as well as the major adobe software groups.  There are just a few entries in the windows system area, that relate to "legacy applications" leave those alone, but everything else that Adobe put in, ESPECIALLY the licensing stuff to do with the user profile -- a long numeric string as a major key in the registry, remove them too.  Any adobe certificates remove too.

Now set another restore point, after cleaning, reboot, then reinstall JUST InDesign.  It should have fixed it.  A lot of work?  You bet it is, all because Adobe cannot acknowledge and fix this serious flaw.  If the cleanse of the system does not fix the problem, you will probably have to redeploy InDesign from a SERVER install, and add the correct number of licenses for the product.  That way, In Design on the server will monitor the license issue and hopefully get it right.

We use per user licensing and not an actual server. Are you referring to allowing Adobe hand out a digital license whenever someone requests it?  When you say reinstall just InDesign, can the rest of the suite be reinstalled afterwards as well? Is it better to install InDesign, reboot and then reinstall the rest of the suite? I agree that this is internal code in the Adobe products that is causing this problem. This only seems to happen to certain people at certain times (we jokingly call it the time of the month).

Thank you for the info