tl;dr Remove all unused modules which have a dependency on the support library from your settings.gradle
.
Long version:
In our case we had declared the support library as a dependency for all of our modules (one app module and multiple library modules) in a common.gradle
file which is imported by every module. However there was one library module which wasn't declared as a dependency for any other module and therefore wasn't build. In every few syncs Android Studio would pick that exact module as the one where to look for the support library (that's why it appeared to happen randomly for us). As this module was never used it never got build which in turn caused the jar file not being in the intermediates folder of the module.
Removing this library module from settings.gradle
and syncing again fixed the problem for us.