Hi Golan,
In this case,i would suggest you to go once again through following steps and check if anything is missing.
1.Create a new user with unique (first five letters should be unique) mailbox.
2.Assign it administrator and domain admin rights.
3.Assign it exchange full admin rights from system manager.
4.Assign local admin rights on exchange serve.
5.Send email to this a/c , check if received.
6.In Backup Exec, Goto menu Network->logon accounts and create a logon account for above.
7.Right click on mailbox and select connect as ,type above name and password. See the result.
Do revert back with details.
Thanks and regards,
Note : If we do not receive your reply within two business days, this post would be marked "assumed answered" and would be moved to "answered questions" pool.