VSS backups fail randomly if Sophos antivirus is installed on the machine.
The way in which the Sophos endpoint agent writes to the Windows registry causes the Volume Shadow Copy Service (VSS) to time out, which causes the backup to fail.
To resolve, follow the steps provided by Sophos. See also this article from Microsoft's knowledge base.
Article is closed for comments.