I see your frustration, and while my environment is likely smaller, I too deal in multi TB data stores.
I'm in the throws of virtualizing my environment. In the physical world, I have to rely on old full backups because it takes too long to take a full backup of a 10TB volume.
First you have to set goals. What are you trying to acheive from a backup solution.
My marching orders are usually to be up and running as fast as possible while losing as little data as possible.
The traditional method still works and is still slow.
I've looked at virtualization aware solution and am leaning towards VEEAM. As a test, a complete backup of a moderately sized VM was 4 times faster than with Backup Exec. And the block level incremental are ridicously fast. Combined with the ability to incorporate the incrementals into the full, dropping the need for regular fulls make it a good, fast solution.
It meets the need of being able to recover at the VM or file level. Depending on the license level and your infrastructure, you may also be able to power up your VM from the backup file.
At some point, you may need to realize that your old backup solution may no longer be viable. You've been through a change in technology and the old tools may not work anymore,