Part of the solution might be for each client to limit the view of notes in the global feed and to replies to those in a “trust graph”.

For instance, you trust the people you follow. You would also trust the people they follow, and so forth.

This extension of trust would allow for a sizable global feed without much spam. Someone in your trust graph would need to follow the spammer to make the content visible. Maybe a few would sneak in from time to time, but they would be easy to block.