Tom White dropped me a note to tell me that he had created an implementation of java.util.Map on top of Amazon S3. As Tom notes, "Normally we strive for an implementation that is efficient in terms of speed, however in this case I was very aware of the monetary cost of each method."
Tom took care to document the number of S3 calls made by each method in his implementation, and, being a faithful S3 user, also stored the JavaDoc documentation for S3Map in S3! This table is quite interesting and should be very helpful to any developer using the class.
Way to go Tom!