Backup Exec Mailbox Restore deleted user fails, error e000848c

Using Symantec Backup Exec 11d and Exchange 2003.
Trying to restore a mailbox of a user who has long been purged from our Active Directory/Exchange environment, receiving the following error: "e000848c - Unable to attach to a resource.  Make sure that all selected resources exist and are online, and then try again. For additional information regarding this error refer to link V-79-57344-33932".
Checking the referenced link, http://www.symantec.com/business/support/index?page=answers&startover=y&question_box=V-79-57344-33932, four possible issues exist. One refers to SAP, one refers to backup of a hidden partition, one refers to VMWare, and one refers to Exchange 2007 or 2010. This is not SAP, this is a restore not a backup, this is not on a VMWare environment, and this is Exchange 2003, as stated.
That said, the only one that is close is the Exchange 2007/2010 item. It goes on to further discuss this error occuring with a mailbox restore redirection, which I am not necessarily trying to do (have tried restore both ways). It also says that this affects BE 2010 R2, which is a later version of BE than we have.
Other searches have indicated that I have two options - 1) Do not redirect the mailbox, and restore directly (tried this, still same error), 2) Upgrade Backup Exec to latest version (not feasible at this time).

Any ideas? The entire backup set is ~350GB, so it takes 4 days to stage it each time I try something, and this is going on a couple of weeks given my attempts thus far.