PoW like hashcash (not a cryptocurrency thing) might be a better solution. Users could even delegate solving the PoW puzzles to a 3rd party for low power devices like phones. But it imposes a cost on spammers that's inescapable.
That assumes spammers are using their own hardware to post. If they're using a botnet, they don't care about CPU cycles. Botnets would probably become even more profitable in that model.
