Gavin, IMHO, transaction fee policy is a business to miners. You shouldn't care, unless you're developing a miner.
I think that the miner that comes with the default client should just be discontinued and removed from future versions. This way, there's no "default policy" and miners will create their own. If they want to accept free transactions they will, otherwise they won't, and they'll find their ways of prioritizing them.
The only thing that the client should be capable of doing is resending a transaction, with a higher fee.
It would also be nice too if the user could specify the transaction fee per transaction. The GUI could also allow different kind of inputs (absolute value, relative to the transaction size, relative to the amount etc)
I think this is a bad idea, possibly very bad...the network has to set the rules regarding what are acceptable blocks and what are not...and with that, what transactions those blocks must include. If it's easy to create transactions that the issuer can be confident the network will drop, it opens the whole system up to rampant abuse and fraud. If this were possible someone could easily craft bitcoin transactions designed to be abandoned and use those for payment...a person could obtain some good or service long before the unsuspecting victim realizes what has happened. This is not a recipe that will engender confidence in the system.
Furthermore, this would put too much power in the hands of miners...it's the responsibility of the network to validate blocks and transactions and to decide what is acceptable and what is not. Not the miners. I cannot stress this point enough. The miners will still have an equal role in setting the market rate for transactions (which is what I think you're after here). Setting aside the current 50btc payout for blocks, if the predominate fee that people are offering is low enough, there will be little incentive to mine (based solely on the transaction fees)...so, mining activity will plummet as will the difficulty. I think what you'd find is that it would get low enough that some merchant would realize they need their transactions verified and would press some old spare PC into service to do the mining (with the difficulty being low, it would be a very cheap thing to do). They would be generating blocks for their own transactions and because of the rules enforced by the network, everyone else's as well. He would prioritize his own transactions (but would have to remain within the guidelines of the network)...other merchants, needing the same service would either run a miner themselves, or start attaching a fee to their transactions. And, soon, anyone wanting to see their transactions clear a little sooner than 4 hours (again, arbitrary number I picked) would start attaching a small transaction fee. Conversely, if everyone is competing to have their transactions verified quickly and bidding up the fee for that, then more people will enter the mining business to capture a piece of those profits.