Ultimately I don't think any open network can effectively deal with spam by either proof of work or by demanding micropayments to take part.

For proof of work, spammers with dedicated machines optimised for the particular work problem at hand can often in a few seconds generate more proof than a user on a low-end android device can generate in multiple human lifetimes. (It can get very silly, like the sun would burn out before the android device catches up.) So spammers will always out-work users.

This same failure mode also applies to micropayments. Spam is an industry. Dedicated spammers will always earn from their spam, be it via simple impressions, or as a front door to some scam or another, or by taking payment to bring someone else's system down, and so on. And it's the dedicated spammers you need to keep out, they will always appear at some point, typically once the impression base seems big enough. (Somewhere in Nostr's future.)

However the amount of money that dedicated spammers can earn from spamming the network is almost always more than what a user in a less developed country can pay to take part in the same network. And sometimes a user in a more developed country too.

Web of trust works to an extent, insofar as trust is paid for by time and persuasion. But web of trust is a perpetual chicken and egg problem, you have to have trust to earn trust and then how do you get started? It makes the new user experience painful, and networks like Nostr already have a high bar to entry, adding this trust-building obligation often means no growth at all, with abysmal retention rates. (That said once you're already in it's a pretty strong option.)

There are answers to the open-network spam problem that seem reasonable to me, but most revolve around small communities, not the town-square. So open networks but in contained spaces, which themselves are walking a fine semantic line between open and closed.