The middle ground is that you require proof of work for free users, allowing paid users to bypass the work.

I agree that making a relay operator do spam prevention, basically as a full time job, is a great way to repeat the mistakes of SMTP.

But our focus, as a community, on mobile clients at this time makes it difficult to pursue without alot of pain in the UX. I think we need to get serious about spam, though. Before natural protocol ossification happens.