Any solution has to make spam expensive. Anything else is just adding further problems.
That's why I like the solution implemented with Litecoins.