Do you have the backup agents for exchange for your Veritas Backup (thats an extra license). You will need it to backup up the Exchange with Veritas, other wise use the NTbackup on the exhange server to backup to the local server (ntbackup is realy not desinged to backup accross a network, so Microsoft Says).
I backup my exchange server (using NTbackup) to the local server, and then backup that backup data to my tape library using veritas netbackup server. You could also use Ntbackup to do a System State and Exchage backup to the local machine and then backup that up with your Veritas to tape. Best method would probably be to have a Exchange Agent for your Veritas.
I found that if you do a full backup up with an Exchange server with backup software that does not have an agent for the exchange, it does not backup the exchange data and there is nothing for you to restore. Found that out the hardway a little while back. Just a tip, make sure that your Antivirus software is not scanning the exchange data, can corrupt it,(use Symantec Mail Security for Exchange). That is how I found out that my Veritas backups of the Exchange Server did not backup the exchange data.