Our "One database per tenant" model was also the reason we were so slow to go to AWS-- the MSSQLServer licensing terms were cost-prohibitive.
However recognizing that around 90% of the FogBugz databases were free-tier and didn't get daily changes meant that teaching the backup scripts to skip creating redundant backups solved most of the issue.
Post-Sandy, I was able to solve most of this by:
1) Shipping full, diff, and incremental backups at different schedules
2) Scripting the ability to create warm standby servers powered by the latest fulls, then diffs as they come online, then the logs at the cutover time. (so you can provision a new server and seamlessly cut over to it)
3) Using our own scripts instead of the RedGate tool (which was _fine_ just not equipped to handle as many DBs as we had) to orchestrate the backups and restores. This in particular was needed for the "only back up modified dbs" fix.
This got us to most of what we wanted-- 0-downtown transitions of databases across servers, nightly offsite backups, fast backup runs. The final problem-- if our datacenter evaporated and we had to reprovision everything from scratch -- was left as an acceptable risk of "we'll fetch the nightlies from s3/Glacier while we do the slower part of rebuilding our servers."
But to your point, during Sandy, none of the above had been fixed yet. I think our sysadmin team was very strong, but they weren't programmers (and/or didn't have enough time to step back and program), and I was able to pick a lot of low hanging fruit in DevOps