Backups failing due to access or VSS problems

We are using Veritas Backup Exec 20.3 (yes I know...) to back up files to tape. The other day, the job backing up shared folders on our SQL server stopped working and after some initial investigation, we found it was two specific directories on one of the SQL VMs.

The Backup Exec error is:

V-79-57344-65033 - Directory not found. Cannot backup directory \Vault\Parts\021 and its subdirectories.

There are quite literally hundreds of these; from \Parts\091 through to \Parts\999.

This occurs too:

V-79-57344-34108 - An unexpected error occurred when cleaning up snapshot volumes. Confirm that all snapped volumes are correctly resynchronized with the original volumes.

The Backup Exec job even fails when we tell it not to back up any open files, i.e. not use VSS.

We have since raised a ticket with Veritas Support and they have suggested it is a VSS problem. They advised us to try backing up the same directory using Windows Server Backup and the VSS Full option. This worked, suggesting the problem lay with Backup Exec.
Now, the WSB job is failing with VSS errors. I've changed nothing on the SQL or backup boxes and the shares in question appear to be fine. I can browse them from both servers.

The WSB errors I can see in the Event Viewer are:

8193 - VSS - Volume Shadow Copy Service error: Unexpected error calling routine IVssAsync::QueryStatus. hr = 0x800706ba, The RPC server is unavailable. Operation: BackupComplete Event Executing Asynchronous Operation. Context: Current State: BackupComplete.

517 - Backup - The backup operation that started at '‎2019‎-‎04‎-‎11T07:47:50.381921400Z' has failed with following error code '0x807800AF' (The Volume Shadow Copy Service backup complete operation failed. See the event logs for more details.). Please review the event details for a solution, and then rerun the backup operation once the issue is resolved.

I can find very little online about these errors and even less about how to resolve them and the failure of WSB is now compounding the problem.

Can anyone help?