TL/DR: A transaction fee market exists without a block size limit assuming miners act rationally.
Transaction fee's are bid to the minimum necessary to include them on the blockchain. This minimum does not magically include all miners, and would reach equilibrium, absent any artificial scarcity, at roughly the cheapest rate possible to achieve that end. That collection of rates would be enough to cover a single datacenter in an ideal location.
The only artificial scarcity in the system is the block size limit. With it, fees can be bid above that equilibrium and thereby fund redundancy of both nodes as well as hashpower.
Without it, nodes would atrophy toward that equilibrium (~1 node). Bitcoin would have failed long before that equilibrium would have been reached, not only because it would mean the goal of a decentralized currency would have failed, but also because hashpower would fall below what would be necessary to keep it secure.
If you're saying that even in that outrageously broken scenario that it would still cost money to add transactions to the block chain, yes you are right. Are you planning on actually addressing the real problems with removing the block size limit?
Yes, probably a better explanation then mine.
The orphan based fee-market brakes down when miners act rationally. The incentive is to always reduce orphan rate and that can be done with 2 datacenters with big pipe between them utilising the methods Greg describes for sending blocks.