Spurious "Unable to locate package " errors on trusty

I get often but random errors that the apt-plugin cannot find a package. Example: https://travis-ci.com/Return-To-The-Roots/s25client/jobs/168946318

There it is g+±8 but it also just happened for g+±6 while the g+±8 jobs succeeded.

In the event of such a failure ALL jobs requiring that package fail (so far)

The .travis.yml has dist:trusty and is not changed between runs. Restarting the failed jobs later sometimes solves the problem.

Anything I can do or is this an error on the VMs?