By the nature of the way that they are done, Mailbox or Brick-Level backups are orders of magnitude slower than stiores backups
Backup Exec has to log on to Exchange, attache to each selected mailbox and then open and "read" each item in that mailbox. This is extremely inefficient, especially over a network
See http://seer.support.veritas.com/docs/235354.htm to determine what Veritas calls a "reasonable time" for Brick Level backups