We need a proof of work change. How low do you think that will drop us?
Something less drastic could also work. Something that wouldn't fck up the "good guys" as much. I'm thinking along the lines of a coinbase penalty depending on mempool size - or something proportional to the average fee of transactions left in the mempool. The main problem I see with such a fix is that it would require a fork. Would a soft fork do? I doubt it, mainly because of the problems with non-upgraded clients.
Won't we have to hard fork for replay protection anyway? (Total noob question.)
Such a coinbase penalty would be messing with the inflation schedule.
Of course it would, but it would be a problem only for the particular non abiding miner. All other parties would see the value of their BTC increase, even if admittedly by a tiny amount. In general, a tighter cap on programmed inflation doesn't seem to be such a big issue.
Also, the mempool is not consistent across nodes. A freshly broadcast transaction may not be visible to everyone. So, we would need mempool commitments. Something like a blockchain could work for that

.
This is more serious and possibly a show stopper. Pity, because automated, mathematical retribution for spammers is every user's wet dream. I just tried my hand at the conceptual level. As someone else pointed out ("go code it, bro, or it's just fluffy talk"), there's probably little need for armchair protocol improvers.