I have a Exchange Server 2003 and media server BE11d.
In the backup task i select all "microsot information store". When i attemp restore a mailbox, I not see all mailbox.
The task backup end success.
Are you doing GRT backups of your exchange?
Is your backup on tape...
Try to duplicate it to disk and see if you expand and drill down the information store..