Backup Exec (10.1 at least) has an annoying (and undocumented) bug when it comes to restoring to an Exchange 2003 Recovery Storage Group. When you go to restore a mail store to a recovery storage group, BE goes along for a couple minutes and then fails with error "V-79-57344-65280 – Unable to restore the selected Microsoft Exchange database 'MailStoreNameHere' because it is currently mounted. Use the Exchange System Manager to dismount it, and then retry the job.". The whole point of the recovery storage group is to restore user data without dismounting the production store, so this doesn't make a whole lot of sense. Recovery Storage Groups are a feature that is transparent to the backup/restore program. Exchange automatically redirects the restore to the recovery storage group as part of the existing APIs.
Apparently the issue is that Backup Exec is doing a query to Active Directory to determine whether the store is mounted, and of course it is. There is a registry key which can be set to tell Backup Exec to ignore the results of this query. To make this change create the following registry value (DWORD) on the Backup Exec server and the Exchange server:
name = "ignore mount state"
value = DWORD(1)