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)