> it was too hard at such a massive scale... of 858 TB

There are probably many S3 buckets in existence that are bigger than that.

Not saying that they should've used S3, but it's definitely possible configure multi-regional backup (and a government can afford it).