There is a setting in Backup Exec for the GRT staging location.
This loction probably defaults to the C: drive of the media server.
It is only used when trying to restore a single GRT object (in your case an e-mail) from a Backup that was done on tape.
It is used to recover the whole of the container the holds the GRT object (in your case this means your information store) to a disk location from the tape because we cannot directly mount the information store from tape in order to get at the individual e-mails. - We mount it from this temp location after it has all been pulled back form tape.
As such where the space needs to be free is NOT the partition that currently holds where you are restoring too, it is purely where this staging area is located.
I am sorry I am not in front of Backup Exec currently to be able to tell you where to go to set the path for this area to somewhere with enough space (that also must be NTFS and must have the same sector size as your original Exchange Information store path)
Note1: This setting is in different places depending on whether BE 2010 or BE 2012 is being used.
Note2: If you did backups to disk instead of tape then the staging process is not needed as we mount directly from the backup. This is why we recommend GRT backups are done to disk (with duplication to tape if you need an offsite copy)
