Lesson for those designing cold-storage solutions--design your system, as much as reasonable, to not support deletion operations. The reason why files get lost is usually due to software bugs, bad configurations, and operator errors. Design your system to protect against these things.
If memory serves, a class of Glacier storage (AWS) isn't practical to use in the EU because the inability to delete makes it impossible to serve "Right to Erasure" GDPR requests.
The set of keys for all your customers should be only a few megabytes, so is much much easier to back up more frequently and more copies of.
It's also easier to have a "we do daily backups and delete any backups after 21 days" policy.