> The receiving server could require proof-of-work for the first message from a sender to a given receiver,

at this point mailing lists are dead

> It could be introduced gradually: if a proof-of-work is provided, then the message is allowed to skip the spam filter.

Yes, because that totally will not harm the small senders (often individuals) whose newsletters can easily reach thousands / tens of thousands.

> Sending email should be free

> Suppose the proof-of-work cost is calibrated such that it costs about $0.001 per email. That would be enough to destroy

all mailing lists, yes. Look at open source mailing lists.