Don't know much about Nostr, but wondered re the spam problem, if it would make sense to introduce the idea of proof-of-work for the identities? A quick search shows that the have optional PoW proposals for notes (i.e., individual posts), but I didn't see anything about PoW for identities.

People could spend $1, or $5, or $50 of compute for an identity, and others could use the cost of the identity as a filter. Having a $5 ID put on a blacklist would make poor behavior of any sort more costly.