We would like to mention you the following.
In the Exchange Administrator, under Site, Recipients will display all mailboxes except for the hidden ones. Similarly, VERITAS Backup Exec (tm) will only back up mailboxes it is able to view, that is, the mailboxes that are displayed in the Recipients container.
If a mailbox is hidden from the Global Address List (GAL), Backup Exec will be unable to view the mailbox. Therefore, the mailbox needs to be made available to the GAL if it needs to be protected by Backup Exec.
To protect hidden mailboxes, it is necessary to back up/restore the Microsoft Exchange Information Store.
-----------------------------------------------------
Veritas has documented this information in the form of Technote as given below.
Title:- How to remove the "Hidden" attribute from Exchange 2000 and Exchange 2003 mailboxes so that the mailboxes will be available to the Global Address List for backup purposes
http://seer.support.veritas.com/docs/243328.htm
As we know that your issue is solved, We apologize for the inconvience caused due to this particular issue.