I like Justus' pay-to-relay idea, but I'm having second thoughts about whether it would actually work.
Consider this thought experiment, there are three otherwise identical cryptocurrency networks. The total cost to do a trustless transaction is the tx fee plus whatever it costs to rent full-node capable hardware long enough to validate the transaction you receive.
A: 1mb block limit, $50 tx fee, validation cost: $0.05
B: 100mb block limit, $0.50 tx fee, validation cost: $0.50
C: 10,000mb block limit, $0.005 tx fee, validation cost $50
Which network do you want to receive payment on, assuming you don't trust the sender or any third party? B. The reason B is so cheap, is that fees are inversely proportional to block size limit, but bandwidth costs are not linear. They're pretty flat until you get up to exotic speeds.
As Gavin pointed out, the optimal block size limit will scale with commodity bandwidth.
So, in the unlimited "pay to relay" model, what forces cause the price to converge at this optimal level? I'd suggest there aren't any. If nothing else, the block reward ruins it. The cost to relay will be insignificant until the block size is so huge, that it takes one of the world's fastest connections to transmit it. By then bitcoin is sunk, or at least depending solely on its head start rather than competing on features and price.
Miners have no reason not to accept all nonzero fees, no matter how large the resulting block is. They do not care if the large blocks knock commodity full nodes off the network. Users care! They'll just go to the hypothetical competing network that's the same, except much cheaper.
Now you could argue that miners are rational and wouldn't do anything to make bitcoin un-competitive. I think that ignores the prisoner's dilemma that would come up.
Let's say all miners know that accepting tiny fees creates huge blocks, causing users to flee to cheaper networks. They don't want to harm their own operation, right?
Some miner will defect, and sweep all the tiny fees from the mempool, even though it creates a huge block. One huge block won't kill bitcoin. Except the miners can't stop at just one. It will happen repeatedly, with no individual miner able to stop it from going down in flames. So they might as well defect themselves and collect every last satoshi while they can.
I think Gavin's got a solid plan. It's got ugly arbitrary constants, but it's simple and there's little doubt it will work.
Would we be able to filll enormous 10GB blocks with transactions if it costs $50 to relay and validate them? I think we wouldn't be seeing many bitcoin transactions if they cost $50 a pop, regardless of how many people use it.
If I'm not mistaken, there's also incentive for miners not to include no-fee transactions because they'd have to pay more to have their blocks propagated quickly.
It sounds like those are at least two of the market forces that would prevent 10GB blocks under justus' proposal.