The problem to adding a cost to email is that it affects everyone. The amount of CPU power you need to waste to make most spam not viable is so much that it isn't worth it.
It definitely does not - you can allow different work loads for different senders. Mailing lists you actually want can be dropped to zero for instance.
Most spam comes from new address pairs, not existing ones. Requiring high cost to get past a first-contact filter, then near zero forever after, is completely reasonable and would practically eliminate unsolicited spam.
But now the sender needs to know the receivers policy and if they remember that there has been contact before. Or I guess you change SMTP but we still allow unencrypted connections so good luck with that.
For newsletter style stuff, nah. The "confirm your registration" email can "pay" to get past the wall, and then you're done - approved pair established, future letters can probably be zero cost and everyone receives the same one.
I wholly admit that this is arguing theoretical setups and that's always problematic, but of course patterns would be established pretty quickly. There are loads of simple tactics that would still make spam dramatically harder, and legitimate use nearly unaffected. The current reputation system has clear, massive gaps that really don't need to exist.
