Solved it a few days ago. Apache on these servers had been configured long ago to run as a different user, not www-data. This did not solve the problem we had back then so we left it as is and forgot about apache. Now that we have Nagios running on apache this caused the problem. So it was a permission issue in the end.
Note: When checking if it is a permission issue, don't just check the file and directory permissions, check that what needs access to them is indeed running as that user in its configuration. In this case it was changed in /etc/apache2/envvars
Lesson learnt.