Will the protocol allow for a free market solution to this? Could one pool offer to process transactions for X fee, and another for Y? While the client doesn't seem to do so today, could the client then be altered to allow the user to direct the transaction at a given pool ("clearinghouse") If it can work this way, then there is no reason to care about the no TX miner - people would direct TXs to the fastest/cheapest processors), and miners not processing TXs would have no effect.
It already does. Miners are free to choose which transactions to include. To date most pools & miners simply include all valid transactions. The subsidy is very high and that is the default option of bitcoind.
All that is necessary is for the client to be aware of the fee policy of all/most miners and the current pending transactions and it could provide a recommended fee (include 0.01 for for 95% chance of inclusion in next 3 blocks, include a 0.0005 fet for 95% chance of inclusion in next 18 blocks).
Of course it is a chicken & egg scenario. If all miners include all tx (fee or not) then there is no real reason for the client to be upgraded. If users have no way of knowing what fee pools/miners require then there is no reason for pools to exclude tx with low fee.
Personally I think two simple thing can happen to get the ball rolling. 1 some % of miners simply agree to not include tx w/ fee below X BTC. If enough do then there will be a catalyst for making the client "network aware". The second event is simply the subsidy cut. If not this one (50->25 then certainly the next one 25->12.5). As subsidies decline the free ride miners have been granting will come to an end.
I am thinking of offering a bounty for a patch to bitcoind which allow for a command line argument (--min-fee x) which excludes work without sufficient fee from getworks. That would allow even p2pool users to set a fee policy.
Honestly, it seems to me that not finding a way for the miners to compete on fees is the real longer term problem. The only way for a miner/pool to make more money is to control more of the network.
Which is why I think a minimum fee other than 1 satoshi will be necessary but we have plenty of time to think about it.