Let's consider all transactions with a fee below some fixed value (say, 20 satoshis/byte) as spam. In this case, the problem can be solved very easily. Just remove the limit on the block size and prevent miners to include transactions(their own too) with a fee below this value into the block… Actually, let's not prohibit all these transactions, but give some space for them (let it be 5%, tentatively):
- the limit on the block size should be removed*
- full nodes should temporarily reject* blocks that consist more than 5% of transactions considered as undesirable (received less than 15 seconds ago | with a fee below 20 satoshis/byte)
- miners should follow the same rules, but in addition, they have to relay and then hold transactions at least for 15-20 seconds before including them into the block
- minTxRelayFee parameter becomes part of the consensus and cannot be higher than 20 satoshis/byte, otherwise, nodes won't be able to check the block for spam
The main idea is that transaction must get into the most nodes mempools and stay there for some time before it can be included in the block. Thus miners are unable to include their own transactions for free and have to broadcast them over the network as all do.
By reserving 5% of space for undesirable transactions we make the condition softer. This is a very large reserve to ensure that nodes always come to consensus. Even if mined block obtained before some transactions that included to it.
* Anyway, the best chain is selected by the amount of work in it. Thus rejected undesirable blocks potentially could be included into the blockchain, but only if most of the miners (>50%) break the rules and accept these blocks with spam. Therefore, during the evaluation of PoW for a chain, nodes and miners shouldn't count these undesirable blocks until they are followed by two or three normal blocks. For the same reason, it makes sense to limit one-time increase of block size in comparison to the average size of the previous several blocks, say not more than twice.