Do not forget that the hard-coded fees constants fix should be addressed simultaneously with this issue since they are inter-linked .... or we'll be back arguing about that eventually also.
We don't have hardcoded fees in Bitcoin Core... except very low ones for relay permission which have been, in practice, below typical. They're kind of ugly, and I'm generally opposed to hardcoded fees, but if they're below behavior in practice they don't cause much harm (and are very very help at preventing resource exhaustion attacks). Bitcoin Core 0.10 has a automatic fee system based on the transactions in the mempool and recent blocks, where you can set a target number of blocks to wait and it will pay based on recent history.
The "constrained" block size scenario makes necessary the ability for ordinary users to increase the fee. Users will want to update the fee on their unconfirmed tx to manage the instability in confirmation times, otherwise their tx can remain stuck in cyberspace, and they are helpless.
This is relatively straight forward to support. When a new transaction comes into the mempool, if it pays at least $increment more fees per KB than the conflicting already mempooled transaction, replace it and forward on. Then you just need fairly simple wallet support to revise a transaction. Petertodd (IIRC) already wrote "replace by fee" code that does this. The catch is that implemented this way it makes zero-confirmed transactions less safe, since you could have a greater success in double spending. This can be addressed by narrowing the set of allowed replacements (e.g. all outputs must be equal or greater), but AFAIK no one has bothered implementing it.
Certainly, protocol block limits should not be hit unless all wallets first support the updating of fees on unconfirmed tx.
Chicken and egg. Without fee pressure there is no incentive to work on software to do that. Most non-bitcoin core wallets just set rather high hardcoded fees (even constant ones that don't related the the txsize metric that miners use to prioritize transactions into blocks.).
Unfortunately over-eager increases of the soft-limit have denied us the opportunity to learn from experience under congestion and the motivation to create tools and optimize software to deal with congestion (fee-replacement, micropayment hubs, etc).
Look at the huge abundance of space wasting uncompressed keys (it requires ~ one line of code to compress a bitcoin pubkey) on the network to get an idea of how little pressure there exists to optimize use of the blockchain public-good right now.
Because they are economically rational and facing different prices for bandwidth and electricity in their respective neighborhoods, they all set different minimum-fee policies.
With correctly setup software there is no relationship between your bandwidth or electricity costs as a miner and the transactions you accept into your blocks, and any slight residual relation can be divided down to nothing by pooling with other N other miners (centralizing the consensus in the process) in order to have 1/Nth the bandwidth/cpu costs. As a miner you maximize your personal income by accepting all available transactions that fit which pay a fee, it's best for you when other miners reject low fee paying transactions to encourage people to pay high fees, but you dont and instead hoover up all the fees they passed up. They take the cost of encouraging users to pay higher fees, you defect and take the benefit.
A more detained explaination is forthcoming.
Sounds good, but hopefully you can understand that some people are not very comfortable betting Bitcoin's future on not-yet-public theorems (which sounds like they must be at odds with the best understanding available from the active technical community _and_ academia...). There have been many "bitcoin scaling" ideas that accidentally turned out to have no security or implied extreme centralization once considered more carefully. There are a few ideas which I think will someday help a lot, but they're not practical yet and its not clear when they will be.