First you need to remember that not all network nodes are necessarily miners. So even if transactions stop at miners, they can still propagate through the rest of the network.
I expect that as network traffic increases and requires significant hardware and connectivity investments, propagation of transactions and blocks will be monetized. So there will be an incentive to operate honest non-mining nodes, and maybe even miners will be incentivized to propagate in spite of the possible competition.
You are probably right, some market mechanism will arise, I just can't imagine yet how the propagation of transactions could be monetized. Bitcoin does not provide a mechanism for that.
It needn't be a part of Bitcoin per se (in fact it could be part of a general p2p monetized data-sharing network). It's easier to see how it will be done with blocks - when a new block is found, miners will want it as quickly as possible and pay to the lowest asking node who has it (they'll need either trust between them or a trusted instant-payment intermediary). Nodes will pay for receiving it from other nodes based on how much they expect to gain from selling it.
With transactions it's harder to micromanage which node has what transactions, but this should be a solvable technical issue.