I'm all for proof of work to rid spam, but probably an easier solution is to harden relays. Then we stop using a relay if it's not hardened and spam ridden.
Discussion
Relays definitely need to do a better job, but clients can also handle this by implementing a sats requirement to show DMs. Want to DM me? Send me some sats first (however much I specify). Client verifies the transaction and lets the DM through.
I like this sort of solution. #[3] is working on this solution for Nostream.