You make good points regarding avoiding overcharging applications and avoiding adding cryptographic assumptions at the protocol level. (Having said that, I wouldn’t rule out the possibility of a constant-sized-witnesses accumulator based only on information theory and hashing, unless there’s a good argument to be made that such an accumulator cannot exist.)
In the context of miner-updated witnesses, we need to be mindful of users being victims of targeted front-running by miners (or other users) that create maximally inefficient trees to push up gas consumption, and possibly even trigger out-of-gas exceptions. This attack is amplified if we go with the pre-state approach. The reason is that a miner can try to grow a maximally inefficient tree with, say, 1000 transactions in a single block and still pay minimal gas for the large mid-state witnesses. In the context of putting witnesses in the transaction’s miner data, the init script that constrains the witnesses can place an upper bound on witness sizes as a mitigation.