Hi I am currently running Backup Exec 11d and also have the Exchange Agent installed (Exchange Server 2003) I have enabled the 'Enable the restore of individual mail messages and folders from the Information Store backups' within the settings for the Microsoft Exchange backup When I go to restore the mailboxes and drill down to the Information Store I can see the Information Store and then the First Storage Group. From the media (Snapshot Full) I can see my 4 Mailbox Stores, but when I expand this I am seeing one mailbox store with no mailboxes, two are showing only a few mailboxes and the last one appears to be showing all the mailboxes. As stated the backup is a Full Backup, not incremental or differential. I don't have the 'Enable legacy mailbox support' enabled either I don't understand why I am not seeing all of the mailboxes I have only just enabled this, and the size of the backups are consistant with my previous backups, so I believe the Information Store is being fully backed up, just not all the mailboxes are visible!
I can confirm that the user account for the backups has a mailbox. I was able to access it via Webmail to prove it is active. The entire Information Store is selected within the selections.
I performed a LiveUpdate today and it installed Hot Fix 27, hot Fix 6 was already installed
My next suggestion would be to get on the latest revision and patches, then attempt the backup again. The latest Revision is 7170 and there is a lot of patches already available for that revision as well. You can download the new revision from either fileconnect.symantec.com or backupexec.com. It's a straight upgrade you should not have to reconfigure any of your jobs, etc. You will need to update the remote agent after the media server has been updated.