All ideas can and should be tried. I'm a fan of simplicity, and it seems to me that the simplest solution is to have the client not show a note at all (in a reply) unless the note paid 1 sat to the OP. Its nothing. It can be lowered to a smaller unit when we get to smaller units. Some spam will still get through, if they pay, but most will stop when they math the total cost of an attack. I'd like to try this solution.

Proof-of-Work is unlikely to be effective for deterring spammers. Spammers easily operate at massive scales (botnets, server farms, cheap cloud). They can absorb the PoW cost more easily than legitimate users because spamming is a numbers game. The meet-in-person (like in the old PGP era) is even less likely to work.