If this really became a problem a much easier solution would be for pools to offer a rewards to nodes that relay them a transaction they haven't seen before. Pools could offer 10% of the transaction fee back to the node that related them the transaction. This could be implement with minimal change to the core protocol and would create more efficient paths for network propogation.
Offering to send 10% back will not
actually solve this problem. If this reward is promised, it is still
etter for a miner not
to forward the transaction.
Solving this problem is not trivial. Otherwise it wouldn't have been worth it to write a paper about it anyway
But I do agree that maybe it's not really a problem that will pop up in reality, if non-miners forward transactions too.