I've been able to improve my partitioning by adding a random suffix from a small set to the key for the writes, and then just trying all suffixes for the reads. Because my work load was relatively write-heavy (used at least ~10x more write capacity than read capacity), and because most of the read capacity was consumed by the size of the entries and not the lookups (so I didn't even have a linear increase in the need for read capacity), I think I came out ahead.

Ultimately, we've decided that dynamodb was not really suited to our use case anyway, but I'd say that's mostly because our total data set was fairly tiny and we our writes were not evenly distributed over time, which is just at odds with the capacity model.