After a while of backing up VMs via vSphere Data Protection (VDP) the backup jobs for four VMs failed. The message said they needed consolidation.
After the consolidation everything started to work for 3 VMs, but not for the fourth. Now I was getting the following error:
Execution error: E10056: Restore failed due to existing snapshot. Job Id: <job-id> (Full Client Path:)
The GUI said nothing about needed consolidation, no snapshots where created, either, and if you look into the VMs config you see that the hdd points to a vmdk, not to a 00001.vmdk snapshot file. So, everything seemed to be in order, right?
After reading some articles I found a vmware KB entry: VDP Backup fails
The solution therein: Old 000001.vmdk-files lying around unused, nowhere referenced or anything. Simply deleting them will help (but an additional move to another location is recommended just to be on the save side).
So with this everything is up and running again! Thanks vmware!