If snail mail cost $0.001 per recipient people would be getting much, much more junkmail. Likewise, if e-mail cost as much as even bulk snail mail, there'd be much less spam.

Some sort of payment scheme is really the best, most durable option. The problem of mailing-lists and personal correspondence could be solved by an exclusion mechanism where the recipient effectively whitelists senders, explicitly or implicitly (e.g. whitelist a replying-sender automatically if a recipient initiates a conversation).