But where's the incentive for a miner to do this?
Offer an extra tx fee for a miner who includes the transaction in a block after making a signed promise.
It can also be the other way around. Miners publicly offer to "support" transactions which contain a minimum amount of fee.
I like where this is going. It seems a cheaper alternative to the "expensive green address" proposal I've seen before, and it is decentralized too.