Hi Steve,
The cheapest and quickest way around this is to go out an buy an external hard drive (1TB or bigger), connect it up to your server, and use this as a B2D target.
Backing up to a shared folder (even when mapped to your local server) doesn't work well, if at all.
To answer some of your other questions:
1. THere is always staging involved when restoring, not so when backing up. Your local staging location, by default, is C:\Temp, but this can be changed. I have attached an article I wrote below if you don't know how to do it. Follow some of the steps to change the defaults.
2. B2D would have to be attached to your media server.
3. You cannot back up individual mailboxes. Backup Exec doesn't allow for this, although it DOES allow for GRT restores of individual mailboxes/individual items.
4. You can look at buying either an external HDD (like i mentioned first), but a NAS box does work. Whatever you buy, make sure it is on the Backup Exec 11D HCL:
http://seer.entsupport.symantec.com/docs/282249.htm
Hope this all helps...?