We suggest you to following to resolve the issue:
1)Apply service pack, SP1 to Backup Exec server. Please refer following technote:
http://seer.support.veritas.com/docs/267180.htm
2) Remove all existing notifications.
3) Clear all SMTP and MAPI info in notification setup
4) Restart BE services.
5) Reconfigure all the SMTP jobs with help of this technote:
http://support.veritas.com/docs/253178
Now check if you receive the notifications correctly .