That really depends on the application, who has access to the keys, how they learn about the keys etc. There isn't a one size fits all solution and that's kinda why eventually consistency is a pain in the ass.

The "I want strong consistency but have to use S3 because its the cheapest way to store stuff and its great at serving reads and just otherwise great" option is to maintain an external index that maps between persistent ids (e.g. file paths) and S3 keys. We use this for hosting user content at my company. Our index is in MS SQL of all things ;)

The MVP option is to not to delete stuff. :) This can work well in some scenarios (e.g. you want to keep all versions around anyway) but be careful to not dig a hole that's hard to get out of.

A more esoteric option is lifecycle based cleanup. This can work well for things like a build artifact cache (where an expired key isn't a big deal because you can regenerate it.)

Some of this is discussed in this blog post by Netflix: https://medium.com/netflix-techblog/s3mper-consistency-in-th... (caveat: s3mper is dead(?) and there is an AWS-native solution for HDFS now.)