What about the following modification:

a1) fold a modified p2ppool protocol into the mainline protocol
a2) require that transactions mined into the mainline blockchain have to be seen in the majority of p2ppool blocks
a3) p2ppool then has an additional function of proof-of-propagation: at least 50% of miners have seen the tx
a4) we can then individually adjust the fees and incentives individually for:
a4.1) permanent storage of transactions (in the mainline blockchain)
a4.2) propagation of transactions (in the p2ppool blockchain, which is ephemeral)

Right now the problem is that miners receive all fees due, both for permanent storage and for network propagation.

Another idea in the similar vein:

b1) make mining a moral equivalent of a second-price auction: the mining fees of block X accrue to the miner of block X+1
b2) possibly even replace 1 above with a higher, constant natural number N.
Late edit:
b3) reduce the coinbase maturity requirement by N
Later edit:
b4) since nowadays the fees are very low compared to subsidy, (b3) would imply a temporary gap of global mining income. Subsidy of block X accrues to the miner of X, fees of block X accrue to the miner of block X+N.
End of edits.

Both proposals above aim to incentivize and enforce propagation of the transactions on the network and discourage self-mining of non-public transactions and self-dealing on the mining fee market.