VDP is being discontinued, and I guess it's because it's a solution that fails to take backup in too many situations. As you've already tried storage vmotion you've already tried some troubleshooting options and you've probably seen these articles as well?
As VDP is basicly Avamar you can also often find answers when searching for Avamar instead of VDP.
Sorry I couldn't be of more precise help. Good luck!
what version of vdp are you running ? Logs show avtar version 7.1.181-107 which I think it's early VDP 6.0 ?
My advice is this, try to take a snapshot of the VM. See if that works. If it does, then you know it's not snapshot related.
I would also look into updating VDP to the latest. It's EOL and most likely you won't get much support soon, but I know people who are still using it with Vcenter 6.5 with no issues.
I've seen a very similar issue on a system that had a storage driver/firmware mismatch, storage I/O would occasionally timeout preventing VDP from cleaning up after itself when backing up VMs. This left the delta disks behind in the VM folder, but vCenter did not list any snapshots on the VM.
Simplest solution for us was to Storage vMotion the VM to another datastore, and then manually delete the old VM folder and it's content (obviously ensure the storage vMotion completes successfully before doing this part). You can either move the VM back to the original datastore or simply re-try the backup of the VM in it's new location.
Obviously the above is just a workaround and does not address the root cause.
Edit: Ah, just noticed you did mention moving the VMs storage to another host. Can you clarify, you did move the storage to another host as well as the VM?