I think we just found a solution as well - but a different one!
We tried stopping the Enterprise Vault File Placeholder Service on the file server and running the backup jobs afterwards. This did the trick! I tried backing up a single folder, containing just one file (an archived file of course). The job completed successfully, and it looks to me like it backed up the EV shortcut for the archived file, since the amount of data isn't zero. The "size on disk" file size was about 4kb, while the backup job of the one file backed up about 8kb. The complete file size was about 200kb.
This means that we could add pre/post batch scripts for our backup jobs, stopping the EV Placeholder service before taking backup, and then starting it again afterwards. Something like:
net stop "Enterprise Vault File Placeholder Service"
and then:
net start "Enterprise Vault File Placeholder Service"