Why not a NIP that would allow relays to ask for a crypto captcha solution before they accept a message? Something like https://github.com/mCaptcha. That would make it expensive to run spam bots, without annoying normal users.