I don't think a idea of a time-based-fee is bad but there is a major problem with deciding what it should be. I mean you can just make up any number you want, but if you are going to bless the idea what the economic holy water of eliminating externalities it should bear some relationship to the actual cost and I don't see any way whatsoever to do that. (Otherwise you are just adding an externality, possibly larger than the one you eliminated.) For one thing the actual cost depends on the number of nodes that are storing it.
As far as there being a cost for waiting longer to dig, that already exists. It's called staking and is a very large cost right now. Over time it will get somewhat smaller. A page or two back we roughly estimated it at about 4% per month. I don't know if that is actually very accurate.
The concept revolves around attempting to estimate supply.
That is where equilibrium (and the possibility of blocksize, which I was trying to avoid) comes in.
The amount that should be charged is the amount that the market is willing to bear.
For any given level of supply (or demand) there is a point on the opposing demand (or supply) curve at which equilibrium is reached.
Where the amount suppliers are willing to supply at a given rate is equal to the amount demanders are willing to demand at that same rate.
If we set a window adjusting supply(block space) inverse to demand(which is in turn the inverse of fee) we reach a point at which the fee charged is the point of equilibrium between the amount demanded and supplied at the given fee.
In short, market/tx demand decides the block size.
Demand is influenced inversely by fee rate.
Block size and fee rate increase in tandem until demand == supply.
At least that is the best I can explain the idea after 36 hours or so awake.
EDIT: There also a few alternative possibilities, such as coin-days-destroyed. In which case, a modulation of coin-days-destroyed would be used to measure network demand for transaction space, adjusting fees accordingly.