I gave much thought to the problem of transaction fees in the last few days and concluded that, confirming a post by Vitalik Buterin
[1], it has no market-based solution. The ultimate reason is that a market requires buyers and sellers while mining cannot become decentralized and still have sellers. Total decentralization turns mining into a public service, and sellers must be private: with only buyers left, transaction fees tend to zero.
Fortunately, I also found a protocol-based solution to the problem, which goes a step further from Peercoin:
1. The reward for chaining proof-of-stake blocks comes from newly minted currency, like in Peercoin—which mints 1% new coins a year.
2. Based on information from the block chain, an algorithm constantly adjusts destructive fees just to offset the newly minted coins.
This way we have both a stable money supply and self-adjusted fees. The newly minted coins transfer value to block miners—from those who skip minting—partially via inflation while destructive fees constantly offset that inflation, leaving a value transfer equivalent to formal payments.
Yet such a value transfer is impossible with formal payments: instead of going directly to miners, its destructive fees go to the whole network as deflation, and only then to miners according to their contribution to the same inflation offset by those deflationary fees.
[1] http://blog.ethereum.org/2014/02/01/on-transaction-fees-market-based-solutions/
