I don't think that the 20MB blocks will be an issue... I don't see blocks getting bigger faster than internet lines being updated. The change will be gradual, we won't have 20MB blocks the day after implementing the change.
As for headers first mining... That's what many are already doing, and that's why some pools forked. As you said, a timeout must be implemented, as very well written in
this post, and well explained in the rest of the thread.
I know what you mean, SPV mining. And i only now realize that competing pools can attack other pools that spv-mine by providing wrong block infos.
But what i meant wasnt mining on header data but building a queue on nodes.
Something like that:
Miner A mines 1 TX blocks.
Miner B mines full blocks.
Miner B finds a block, he propagates the headers to the nodes he is connected to. All nodes spread the headers to others and set this headers on top of the queue.
In the meanwhile the big block from Miner b propagates slowly.
Miner A finds a block. His block is very small. He spreads his header data. Nodes receive them and put them on position 2 in queue.
The block from miner A gets to all nodes. He gets verified completely and is valid. And the headers match that were previously sent.
The block from miner B gets in later. He gets verified and is valid. Headers match too.
In that situation the block from miner B would have been orphaned when his big block gets propagated to >50% of the nodes later. But with the queue the nodes would know that that block actually was found earlier and the block from miner A would get orphaned instead.
That way the advantage to mine empty blocks will vanish and the network will work more healthy. A big problem with more and more miners creating such blocks will diminish.