But for this level of flexibility no hard limit will probably do. What is needed then is no hard-limit at all and a way to make sure that miners respect some dynamic soft-limit.

Now what if the maximum allowed block size will depend on the minimum transaction fee in the block?

So if you have lots of tiny transactions, you won't be able to generate big blocks (protection from attacks/unimportant txs).

But if Bitcoin becomes more popular and there are lots of people willing to pay higher fees, then you can generate larger blocks and stuff more txs in them.

Granted, this is far from perfect, and it will probably be hard to convince miners, but since we need to price in the cost of transmission and storage, it might be better than a simple hard-limit curve.