Solution: Publish mail-enabled BE account in the GAL, as per this document. I'll leave my edits in place for troubleshooting purposes of other people.
Check the status of the Exchange VSS writer. From a CMD prompt, type VSSADMIN LIST WRITERS. A list of writers (including Exchange) will output. They should all be in {1} stable condition.
On the restore, make sure that you have the "Restore to Server" field properly populated.
EDIT: From here:
Ensure that GRT is enabled before you
run backups if you intend to be able
to restore individual items. You can
enable GRT for all backup jobs in
Tools > Options. Or you can enable GRT
for individual backup jobs on the
Backup Job Properties dialog.
Back up your current or most recent
GRT-enabled backup jobs to disk. It is
more convenient to work with
GRT-enabled jobs on the volumes that
do not have file size limitations. You
can create duplicate backup jobs and
send copies of your backups to tape
for archival purposes.
Use a backup-to-disk folder on a
volume that does not have file size
limitations as the destination for any
backups that are enabled for GRT. An
NTFS drive is an example of a volume
without file size limitations. Some
examples of volumes that have file
size limitations include FAT and FAT32
volumes.
Review the requirements for staging
locations in the Administrator's
Guide.
You must use a staging location for
GRT-enabled jobs in the following
scenarios:
You back up to or restore from a
volume with file size limitations.
You restore granular items from tape.
You run an offhost backup job.
Use a volume that is not your system
volume for a staging location. The
volume on which the staging location
resides should have at least as much
available space as the size of your
largest GRT-enabled backup job. You
can change the default staging
locations in the default backup and
restore option settings.
I'm going to have to look a little closer at BE2010 restore procedures, which will be later, but I would start with the above. Maybe it's because you're not staging it?
EDIT 2: Are you using incremental backups?
GRT restores will not work for individual mailboxes or items if the backup was to tape. From this document page 314:
Backup Exec must have access to a uniquely
named mailbox within the Exchange
organization for backup and restore of the
Information Store.
See “Requirements for accessing Exchange
mailboxes ” on page 1081.
You cannot restore individual mailboxes and
messages if both of the following conditions
exist:
■ The incremental or the differential
backup method was used.
■ The destination was a tape device.
If you create full, differential, or incremental
backups, GRT-enabled jobs have the
following restrictions:
■ The full, differential, and incremental job
templates must be part of a policy.
■ The destination device must be a
backup-to-disk folder.
■ The backup sets from the full,
differential, and incremental jobs must
be on the same volume.