Did you notice this line:
In order to back up these files the Exchange Agent must be installed...
Veritas has several Agents (optional add-ons) for Backup Exec. One of them is the Exchange Option (from Veritas' white papers):
Agent for Microsoft Exchange Server *
Fast, flexible technology to protect vital Exchange
Server 5.5 and 2000 data while the application is
online. This agent provides full or incremental, or
differential backup and restores of all Exchange
Server components- including embedded objects,
attributes and all Outlook components. The Agent for
Microsoft Exchange Server gives administrators the
flexibility to perform full, incremental or differential
individual mailbox backup with selective restores of
individual public folders. Using the Single Instance
Storage feature eliminates backup of duplicate
information by storing only the first instance of
attachments distributed to multiple mailboxes. The
agent for Exchange also enables automatic recreation
of a mailbox and user account during restore --
allowing administrators to easily manage backup and
expedite recovery of data, while consuming less
network, system and media resources.
I believe your backups are failing for the same reasons as the other responders stated...you need the Exchange Agent.
-SQLBill