The reason is that the state trie will never hold more than, say, 2^100 elements and a concrete cost of ~log(2^100) is small enough to charge everyone for.
Strongly disagree! That basically means that we would have to overcharge ~10-100x for SLOAD/SSTORE in the normal case, which would really harm applications. My goal here is specifically to charge less for super-small tries (eg. contracts which only have 1-10 data fields) and more for super-humungous tries.
Find or build an accumulator with constant-sized witnesses.
I generally want to steer clear of using fancy accumulators at protocol level, as I have the goal of making the base protocol depend only on information theory and SHA3 as cryptographic assumptions. That said, you can totally make your own contract that uses some fancy accumulator scheme, and it’ll be almost first-class (almost because you won’t get the benefit of miners auto-updating the witness if multiple actors send a transaction to modify the same accumulator at the same time).