Simple: when data is added to S3, immediately bill the full cost of storing that data until the end of the month (or fail the upload request if there's not enough quota left). If the data is deleted before the end of the month, refund the remaining storage time.

To prevent cases where users can upload an excessive amount of data on March 31 that they then can't afford the April bill for, AWS should also maintain a "next month's balance" limit that gets handled in the same way.

It would take a bit more work to correctly handle things like ephemeral data and tiered storage classes, but it's not insurmountable.

You could apply the same kind of billing to most other long-lived resources, including VMs that run business-critical services.