Another interesting thought in this area is Greg Maxwell's suggestion that you could make the block difficulty depend on the block size. A transaction with high fees could not only ensure you get into the next block, it also could increase the probability that the next block will be found quickly, because miners are incentivised to drop their block size and reduce the difficulty to increase their chances of collecting the fee. This also scales up in the opposite direction where needed to handle a capacity crunch, because if you've got a long tail of transactions waiting with a reasonable cumulative fee, you're incentivized to stretch out the block size to accomodate them.