We did end up restoring some large percentage of machines from backup, eventually, then after retrieving/reviewing data we trashed those machines and rebuilt them. We also ended up paying - some of the backups didn't work, and some were taking so long to restore it didn't make sense to wait for them - and we rebuilt those as well.
At least for us, we probably could have done a better job with testing backups. The behavior we saw with individual test restores was not the same as the what happened with mass restores, and we were surprised by that. Also, beyond just restoring from backup, we spent a lot of time rebuilding machines; if you get compromised, your backup might be clean, but the restored state is probably ready to be compromised again. I don't remember how long it was before our security people said they figured out how we got compromised in the first place.