Hi Fredrik,
I think I have seen something similar to this before.
It's because the Display Name of the mailbox used to backup the mailboxes is different to the backup Exec server account name.
So for eg. if the service account is called veritas - make sure the display name of the mailbox is the same as well.
Harry