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.
My guess is that online wallet services (like instawallet etc.) or similar services will have an incentive to speed up the transaction propagation, but then again they might choose to only propagate transactions that their clients are involved in.
So the generalized question is: could the incentive to leach by choosing to propagate none or only a subset of the transactions become dangerous to the bitcoin network? why should any "rational" node propagate any transaction that does not directly benefit you?