You mentioned "90% of the time, my Exchange 2000 server backup job reports 'Completed with Exceptions'".Its seems the ACTIVE FILE EXCLUSION feature is disabled in the registry.
Bydefault, this key is ON, which means it excludes any INUSE-OPEN files.
VERITAS Backup Exec (tm) (version 9.x and later) uses the Active File Exclusion feature to eliminate the Microsoft Exchange Server, the SQL Server, the SharePoint Portal Server, and the Lotus Notes/Domino flat-files from the file system backup. This will prevent "in use - skipped" errors on the .EDB, the .STM, and the .LOG files.
http://support.veritas.com/docs/259152
Incase you dont want to Enable this feature, then either EXCLUDE the Exchange\MDBDATA directory or Stop the "Exchange Informaton Store" service which may not be feasible.