In principle, "pay me a small fee if you're not on my list, if I put you on my list now it's free" would work well (optionally refund someone who contacts you out of the blue that you approve of), but there's a lot of both engineering and social details between where we are now and such a system.

It doesn't take much cost friction to deter mass spamming. I don't think much problem would be left behind from the handful of overconfident spammers who think that they can bust the odds and it's worth 25 cents a message or something.