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.