I have provided some information for troublesooting. I hope it helps.
This issue could occur if the "Job Log default options" is set to "Summary Information, directories, and files processed" and the notification is configured to include job log. This in turn, takes more CPU cycles to process the big job logs and may fail to send email notification.
To resolve this issue, set the "Job Log default options" to "Summary Information only".
1. On the Tools menu, click Options
2. The Options - Set Application Defaults dialog box appears.
3. On the Properties pane, under Job Defaults, click Job Logs.
4. Select the option: "Summary information only".
If the above does not resolve it, then it may be do to an authentication issue with the mailbox on the SMTP Server. If test notifications are successful, but the notifications fail when the backups run, this is most likely the cause. Launch Outlook Express on the media server, connect to the mailbox on the SMTP Server, and do not disconnect from it. Run the backups and if the SMTP Notifications function, then there is an authentication problem.
Some of the related technotes:
Simple Mail Transfer Protocol notification is configured and enabled within VERITAS Backup Exec (tm), but no notification is received after the job runs.
http://support.veritas.com/docs/264683
VERITAS Backup Exec (tm) 9.0 for Windows Servers randomly fails to send notification email http://seer.support.veritas.com/docs/261438.htm
Email notification fails without returning any error messages
http://seer.support.veritas.com/docs/190533.htm
