Hello,
As mentioned in the technote given earlier that this can only happen if the original backup job was completed using VERITAS Backup Exec (tm) 9.1 revision 4691 with Service Pack 1 and Hotfix 33 applied, and the job property for Exchange Enable single instance backup for message attachments was enabled.
One possible workaround for this issue is to use the "deleted items retention" or "deleted mailbox retention" function built into Exchange Server 2000 and 2003. Another solution would be to utilize the Recovery Storage Group feature in Exchange 2003 if possible. Alternately, the attached file, or files, to be recovered may still exist in an alternate location
This is the known issue incase of Backup exec v9.1.
We suggest you to upgrade to Backup Exec v10.0
NOTE : If we do not receive your intimation within two business days, this post would be marked assumed answered and would be moved to answered questions pool.