After some thought, I want to discard my earlier proposal where the block size is adjusted to keep the sum of the subsidy and fees at 50BTC (or some constant). I think that over time, a rise in the value of Bitcoin will hurt demand for transactions, since they will be so expensive.
Here's some more elaboration on what I consider my best proposal, the voting method:
1) A boolean flag is added to each block. The flag represents the block solver's yes or no vote for increasing the block size. The independent miner or mining pool sets this flag according to their preference for an increase.
2) Every time the difficulty is adjusted, the number of yes votes is counted from the last adjustment. If the number of yes votes is greater than 90%, then the block size is increased by 1%. Both percentages are baked-in constants, requiring a hard fork to change.
It occurs to me that a miner could easily code up a function to output the necessary yes or no vote, based on observable network parameters. Here's an outline:
1) Beforehand, the miner assigns a manual constant FIXED_COST which is the estimated additional expense priced in BTC of carrying blocks that are 1% larger.
2) Every time transactions are chosen for a block, the mining software puts together two candidate lists of transactions. One is the normal list which fills up to the current MAX_BLOCK_SIZE. Presumably, it is optimized to include the transactions paying the highest fees per kilobyte. The second list is put together in a similar fashion, but it filled up to MAX_BLOCK_SIZE plus the 1%. It is the first block which is hashed and mined.
3) To determine whether to vote yes or no, the mining software compares the sum of fees between the regular block and the larger block. If the fee increase afforded by the larger block is greater than the FIXED_COST, the mining software stores a yes vote into the block to be mined.
Using this technique, information about the transactions in the memory pool can leak into the blockchain in a way that doesn't require trust and cannot be gamed. The transaction memory pool will influence the decision of increasing block size, but only in a way that preserves the fees.
Since the block size never goes down, we are not vulnerable to the problem where Bitcoin appreciates so much that fees become prohibitive - users will simply send transactions with smaller fees. We also avoid the problem of killing demand for transactions from fees that are too high. Once the fees in filled blocks reaches the equilibrium point, miners benefit from including additional transactions with equal fees and therefore will vote yes (as long as it covers their FIXED_COST).
I believe this is the best proposal on the table. Have at it