One of the proposals floated about, originally from Gavin or @sipa IIRC, was modelling the mempool after a "superblock." This idea seems to elegantly solve a few problems.

Model the memory pool as one big block, whose size is constrained to X 1MB blocks. This super-block is sorted according to default bitcoind block-building rules: fee per kB, with a little area for under-fee (zero fee) high priority transactions. Any newly arriving transaction is either (a) added to the memory pool, possibly triggering removal of other transactions, or (b) dropped and not relayed.

This would seem to deal with spam dynamically, as transactions would drop off the low end of the superblock. This also effectively caps the size of the memory pool, reducing DoS attack surface. And, it plays into transaction lifetime work (#3722).