The scenario.
Two servers – one with Backup Exec 12.5 and all available patches – the other with Exchange 2007 SP2 nd the backup exec agent for exchange. Both running Server 2008 r2.
The problem – every time an exchange backup of the store on the second server failed immediately on backup exec with a VSS error.
The client had mentioned that Windows server backup was failing to start on this particular machine – so I wondered if the two things were related. Tested and found that the WBS software seemed to hang trying to load the details of the machine.
Removed the Windows server backup component. Reinstalled and then ran a windows backup which succeeded. Retried a backup exec backup and it started without error.
So next time you have VSS issues – check if the Windows system backup can run first.