I pondered something similar once.
I'd start with the "email postage" proposal—the one where either a proof-of-work or physical payment (which can also be digital, e.g. a Bitcoin private key) is required to get an MTA to take your message. This proposal was declared unworkable due to rendering high-volume transactional email impossible.
But then:
1. as you say here, divide everyone's email account into a set of "channels" (i.e. subaddresses in a+b@c form, that each have a corresponding message signing key), with one or more published or well-known channels, and then individual private channels for each contact/list, or for each conversation(!);
2. make MTAs aware of "channels", and extend both SMTP and email web services to allow users to configure their provider's end-of-line MTA, over-the-wire, to set the amount of "postage" required to message each channel they own. (This way, the MTA doesn't have to be aware of the distinction between private and public channels; they're just destination addresses with a stored config parameter.)
3. make the MTAs that use channels, reject any Internet message directed to the base address without a channel. (Messages generated by the MTA itself can arrive without a channel.)
4. Set the clients' default new-channel configurations such that public channels have a cost, and private channels are free.
5. In email clients, add a "Subscribe" or "Allow" action-bar item to messages that identify themselves as email-confirmation/newsletter-opt-in emails (presumably with a header), that, when clicked, creates a new channel for the sender, and replies to the message with the signing key you want them to use attached. (All this would be hidden from view; the reply message wouldn't end up in your Sent Items.)
6. In transactional-email-sending services like Sendgrid/Postmark/etc., create a distinction between "opt-in messages" and "ongoing transactional messages"; allow each account to send one "opt-in" email to each previously-unknown destination-address (and charge for this); but then, for that account, put that destination-address into holding state, where the account can't send them any "ongoing transactional messages", until the email-sending service receives the user's conversation key. (You probably want to allow accounts to re-send the opt-in email after a 24-hour-cooldown, though. Though they'd have to pay again!)
7. In any product/service backend that uses a transactional-email service, consider new signups unconfirmed until the transactional-service reports (by polling or webhook or whatever) that the user has replied with a key and is now in the "authenticated and free to send to" state.
A bit complicated in the initial changes, but in the ongoing state it's nearly ideal: it costs money to initiate contact with an address, or to continue pestering an address that doesn't want to speak with you, but not to send messages to someone that wants to hear from you. (Though, a user can "unsubscribe" from your list simply by telling their MTA to begin charging you to deliver to their channel again—maybe, UI-wise, by just deleting the channel. Transactional-email sending services could detect the bounced-with-payment-required delivery error, and put the user automatically into an "unsubscribed" state, which could webhook you to let you know!)