Earlier quoted context omitted.
> We got a shitload of AWS credits for our trouble, but the company obviously went through a very near-death experience, and to this day I don't 100% trust cloud backups unless we also have a local copy created regularly. Cloud backups, and more generally all backups should be treated like nuclear profliferation treaties: Trust, but verify! If your periodically restore your backups you'll catch this kind of crap when…
Are there any guidelines on how often you should be doing restore tests? It probably depends on the criticality of the data, but if you test say every 2 week, you can still fall in the OPs case, right? At what size/criticality should you have a daily restore test? maybe even a rolling restore test? so you check today's backup, but then check it again every month or something?
For physical backups (ex: wal archiving), a combination of read replicas that are actively queried against, rebuilt from base backups on a regular schedule, and staging master restores lesa frequent yet still regular schedule, will give you a high level of confidence.
Rechecking old backups isn't necessary if you save the hashes of the backup and can compare they still match.