Exchange 2010 backups fail (sometimes)

I have had intermitent issues with one of my Exchange servers backups failing.

Both servers are Exchange 2010 SP2 w/rollup 3

Only difference is the server with issues has Server 2008 Stnd SP2  (NOT R2)

some nights backup is fine, and sometimes the backup fails within a minute with error

e0000391 - Backup Exec attempted to back up an Exchange database according to the job settings. The database was not found, however. Update the selection list and run the job again.

and sometimes it runs about 45 minutes and errors with

e000038d - Backup Exec could not back up the Exchange database because it could not find a healthy copy of the database.

the remote agent is up to date on this server.

It also will fail if I try to run it after it fails.

I have found in the server event logs when it fails immediately

Event ID 9782 - Exchange VSS Writer (instance 8afeae75-cdeb-4042-ad45-642c11cbd610:37) has completed the backup of database 'Mailbox Database 1786741976' with errors. The backup did not complete successfully, and no log files were truncated for this database.

when it fails after the 45 minutes I see VSS successes.

I see no errros when I check the VSS status     run  - VSSADMIN LIST WRITERS

when I ran SGMon I was seeing this in the logs

BESERVER: [11/06/12 08:46:09] [0000]     [14560]"Cluster" key does not appear to be present in the registry
BESERVER: [11/06/12 08:46:09] [0000]     [14560] Failed to open Microsoft cluster ()
BESERVER: [11/06/12 08:46:09] [0000]     [14560] VCS cluster keys do not appear to be present in the registry
BESERVER: [11/06/12 08:46:09] [0000]     [14560] Failed to open VCS cluster ()

Thsi server is not in a DAG

Not sure if this is a MS issue or a remote agent issue.