Hi Julian.
local file system: Well at least that crosses one thing off the list, since network file systems can sometimes introduce some inconsistent behaviors.
Permissions: Since all permissions appear correct, I am now wondering if you by chance did a find command on the dataroot to find files or directories that aren't owned by www-data user. The group should not matter if the user ownership is correct. Perhaps this is what you already did to confirm the user owner, but if not, you might give it a try*:
find /var/moodledata/ \! -user www-data -print
That find command should find all files and directories that aren't owned by www-data.
Next, you might look for files and folders that are not readable or writable by www-data. I think this command might do*:
find /var/moodledata/ \! -perm -u+w
*Note: you might need to run those with sudo.
The other idea I have is to review your config.php and see if you are using alternate directories for temp or cache. By default, those directories go into the dataroot. However, in config.php you can override that and set separate directories. If you happen to be using a different path for temp, cache, or localcache directories, then maybe have a look at the permissions on those directories too. You might need to use the find commands like above.
Could it be anything to do with the Database: No I do not think this has anything to do with the database at all.
If those find commands turn nothing up then I begin to suspect other filesystem problems, though not sure what that would be right now (especially since you are on local filesystem). Would be curious to know your Linux distribution/version, and what filesystem is being used.