Let’s assume that the max fee bids are exponentially distributed on the interval [(1+a)basefee, infinity] with rate parameter lambda. The premium will have an exponential distribution with rate parameter 2lambda. The median will be a/2 + ln(2)/(2lambda). It suffices to have a > a/2 + ln(2)/(2lambda) that is to say a > ln(2)/lambda. If a is for example 2% then lambda can be as low as 1/3, which is very heavy-tailed, and everything still works fine.
I don’t want to repeat myself, talking about the robustness of the median, so let me ask your opinion about another point, which I didn’t want to bring up at first, just to keep things simple. Do you agree that this incentive and attack you are talking about is a consequence of the asymmetry between the base fee and the premium? That is the miner doesn’t care about including more transactions because he won’t get any portion of the base fee. In sharp contrast, he gets 100% of the premium. My previous path-dependence attack is also incentivized because miners like to drive the fee into zero and fall back to the first-price auction mechanism. Why do you think this asymmetry is essential?