I think I have found the cause of the Job Failure alerts. I was taking the jobs off Hold Status two at a time and watching them run. I had almost all of the jobs completed when they started to fail again with the same error as before. I checked the Services applet in Computer Management and the Backup Exec Job Engine service was stopped. Upon further investigation I found the following errors in the application log:
=========================
Source: DrWatson
Event ID: 4097
Description: The application, C:\Program Files\VERITAS\Backup Exec\NT\bengine.exe, generated an application error The error occurred on 09/15/2005 @ 20:51:19.196 The exception generated was c0000005 at address 00320031 (catcommon!SQLQuery::BindCol)
=========================
=========================
Source: Application Error
Event ID: 1000
Faulting application bengine.exe, version 10.0.5520.0, faulting module catcommon.dll, version 10.0.5520.0, fault address 0x00010031.
=========================
It looks like the service is crashing for some reason...?