One simple change which could be done quickly is to remove the min mandatory fee rules (which only apply to low priority/spam txs) related to block inclusion and keep the lower min mandatory fee rules for relaying.

For those who don't know the QT client (and many other clients copy these same rules) enforces the following fees as a denial of service prevention mechanism:
1) For high priority txs - no fee required *
2) To relay low priority txs - 0.0001 BTC per KB  (0.1 mBTC per KB)
3) To include tx in a block - 0.0005 BTC per KB (0.5 mBTC per KB)
4) To create a low priority tx - 0.0005 BTC per KB (0.5 mBTC per KB)

The third and fourth rules can probably be removed completely.   Miners are free to set their own fee requirements anyways and malicous users would simply use a modified client anyways.

So the rule set could be reduced to this:
1) High priority txs (create or relay) - no fee required *
2) Low priority txs (create or relay) - 0.0001 BTC per KB (0.01 mBTC per KB)

At the same time the relay (but not create requirement could be reduced to 0.00005 (0.05 mBTC).  The reason you can't change both at the same time is that older clients will reject those txs so you don't want to drop the create rule until a super majority of the network has upgraded.  Once a super majority of nodes has upgraded a new client version could be released which creates tx which will be accepted by the upgraded nodes.  Longer term Gavin presented some good ideas for starting to build a "fee marketplace" but this could be an interim step.   It could even be done in the next version and release in a relatively short period of time.

Also the default optional fee should be lowered from 0.01 ($1.34) to the min mandatory fee (either 0.01 mBTC or 0.05 mBTC).


* Now remember miners are free to impose their own fee requirements and often no fee high priority tx have to wait many blocks for inclusion so optional fees may be useful in a lot of cases but these would be between the miner and clients, the protocol wouldn't care.

if we popularize modified clients and have the above mentioned zero fee policy nodes in place, we are basically there.

The basis for a marketplace is price information. We need realtime statistics about actual fees paid by others to be displayed in the client when people go to send coins. Then a fee market would develop naturally, with miners never getting shortchanged, users never overpaying, and no one wondering how much to pay or whether their transactions will go through. Most users would probably just have the fees default to the market price, or a bit higher if they need to guarantee confirmation in a reasonable time.

Partly this is a temporary problem caused by the block size throttling that's in place until May 15th. Once we hard fork the <0.8 nodes out of the system miners should start raising the block sizes they create up to the 1mb limit, and at that point transaction backlogs shouldn't build up even if you aren't attaching a high fee.

So in the short term, what can be done is:

1) Wait until the May 15th fork. After that point, transaction backlogs should not be building up unless there's a lot of suppressed demand.

2) Fix various clients (e.g. bitcoinj) to correctly calculate minimum needed fees so they aren't constantly outbidding other clients and wasting their users money.

I won't have time to do (2) for a while, so we need a Java developer who is willing to step up and write a few patches.

My guess is you didn't read anything I wrote.  I addressed the fact that miners are free to set fee policies and sometimes even high priority tx need a fee for timely processing.
I also addressed the fact that there is no reason to change the limit a client imposes on creating new tx, until most of the nodes have ALREADY been updated to allow relaying.

Nowhere did I indicate that x min fee would always get a tx in a block.  It hasn't never been that way, not today, not since block 1.  Miners have always been free to pick which transactions can be included.  However given the fact that miners ARE ALREADY FREE TO INCLUDE THE TX THEY WISH and market demand has resulted in miners ROUTINELY DELAYING LOW FEE TX there is no real reason for the extra fee rules.   

Simple version (for those who like to only skim and point out errors which don't exist):
Let miners set their own pricing and have the client only enforce a min fee on creating & relaying (i.e. 0.0001 BTC).

if its that ripped of and miners are making such a big profit....set up a mine?

Now I'm curious about this potential product. A space that tracks and informs on current fee rates could be instrumental to the basic functioning of mining. The fee always struck me as a sort of tip to making mining worthwhile for people doing it (aside from the current potential reward). Since fees could determine the priority of a miner to grab a particular transaction and bundle it or prioritize--i.e. the confirmation in time concept mentioned in Zangelbert's post.

Fees following market costs (or to USD, to EURO, etc.) would make more sense to allow people to make transactions without smaller ones getting swamped with the transaction fee. Since as the value increases, smaller bitcoin fractions will become used more often.

Thing is you cannot establish the price of the fees without involving an exchange, even then what would you hedge it to?

when I said: "lower the fees!"

I did not mean you should crash the exchange rate, OK?