I run a service which writes around 50-80 million small documents into S3 per month and, like you, we spend more on PUTs than storage and retrieval. So reducing PUT costs is something we've looked into a few times.

We do make heavy use of the S3 versioning API to let us roll back files, lifecycle rules for past revisions and have never been able to find any service which offers the same amount of functionality with reasonable pricing.

One thing we have done which has saved us quite a lot is adding a buffer between our service and S3 which delays file writing by up to an hour in case an updated version of a file is uploaded. This lets us limit our PUT requests but still gives us hourly revisions of files if we need to roll back. Without this system we'd be looking at over a billion writes a month. Certainly not a strategy suitable for everyone though.