The simplest solution to spam is requiring the sender to pay the recipient money, e.g. by sending a zap or an ecash token along the message.

But we've all grown so entitled to free technology, I can understand why it's a hard pill to swallow.