I like Gavin's proposal. (I mean his actual proposal, not the "half-baked thought" quoted above.)
No hard limit, but nodes ignore or refuse to relay blocks that take too long to verify. This discourages blocks that are too large, and "spam" blocks containing lots of transactions not seen on the network before.
This might create an incentive to mine empty blocks. To discourage this, in the case of competing blocks, nodes should favor the block that contains transactions they recognize, and ignore (or delay relaying) the empty block.
That might work, though I'm worried that with such rules blocks would become gradually larger and over time the number of full nodes would shrink dramatically as weaker computers get separated from the network. For example, dial-up nodes would get separated right away. No one would care that dial-up users can no longer run full nodes, and they would themselves mostly just say, "Oh well, I guess my setup is too slow to run a full node. Time to switch to a lightweight node." This is probably reasonable for dial-up, but I think that it might over time spread to most people. As blocks become larger, people on average PCs would have to switch to lightweight nodes, then even hobbyists, and then even small businesses.
Maybe there should just be a planned hardfork every 4 years (or whatever) where the max block size is set to something reasonable and other fixes are made.