Frustrated,
Why are you doing mailbox restores on a regular basis? Thats what the delete items retention is for. And why do you have 500GB databases? Are you building 25TB Exchange Servers?
Why not shrink the database down to something a little more realistic, like 100-200GB (or even less) and make sure that the deleted item retention is set for a realistic number.
Then users can restore deleted items. And if for some reason you have to do a mailbox recovery, then it should only take a very few hours.
But in general, absolutely, telling the boss that it is going to take a day or more to do a recovery is a VERY GOOD THING. That means that they won't want to do it when they feel like it, only when it is absolutely required.
What the heck do they do with their paper document? Do they leave them downstairs for a month just in case they want them back.
Deleted is Deleted, they just have to learn that. The Exchange Team gives a user a chance to not only go into the trashcan, but after it leaves the trashcan, it can be recovered up to the dumpster timeframe.