First, I wanted to say, you bring up some very good points. S3 wasn't really designed to be a searchable key/value store, as you have to pay for lookups, and pagination kills your ability to effectively search anything greater than a few thousand objects in a hierarchy, within a reasonable amount of time.

There are, however, ways to solve this: you could fire a Lambda function whenever an object is put into your S3 bucket that simply adds a single row to a DynamoDB table with the object name, along with any additional metadata you might like to capture to assure data provenance. Then, to search, you can simply query the DynamoDB table.

As always, there are many basic building blocks at AWS, but you have to connect them together (like legos) before they become useful for most applications.