Todd - I backup (Exchange) of approx 130Gb, 350 mailboxes.
I am still using 10.0d.
Backing up Information Stores with verify (but NOT mailboxes) takes approx 1hr 45min.
Your overall throughput when you include mailboxes is NOT unusual.
That's one reason why I don't do them - it blows the backup window out for anything that follows.
Also, I have had no real need to recover an individual message - Exchange/Outlook gives the end-user the ability to recover deleted items.
Also, when someone leaves the org, we use ExMerge to extract that mailbox to a *.pst and archive that. So, when historical data from that person is needed, we give the person access to that *.pst.
One strategy for you might be to separate Information Store backup and mailbox backup. After all, if your Exchange server is 'lost', it will be the IS store backup (done with 'flush transaction logs') that you need to re-create your Exchange system. Maybe IS backups through the week, and a maibox backup on the weekend.
We discussed a lot here about mailbox vs/and Information Store. Do read what is in the BE admin guide. Also, look carefully though the event logs on your Exchange server - around the times of your Exchange maintenance and all the events generated as an IS store (with 'flush logs') runs; I'm sure you will realise how important this is.
In the end, we saw IS backup not as a 'work around', but the "proper" way to back up Exchange.
I will definitely be investigating the Granular Recovery of 11d - but not at this early stage of the product life; let someone else sort out the bugs!
Cheers