> Make spam expensive using proof of stake

That's already a thing. Hashcash [1], the PoW algorithm underpinning Bitcoin, was originally conceived as a method to prevent email spam.

[1] https://en.wikipedia.org/wiki/Hashcash