The best way I found is recaptcha on signup to stop around 90% of spam bots, and shadow ban trolls so they can still see their activity but no-one else can.
I hate reCAPTCHA, and I also dislike being unable to see messages that someone posted if they have been posted intended to be public.
You are free to implement your own instead of using Google's implementation. Unless your disagreement is with the concept.
My disagreement is not with CAPTCHA in general; some simply ask you a question in text and expect you to fill in the answer, and that is reasonable, I think.
Use the robots9000 approach. No duplicate posts allowed. It works well for /r9k/ and for some various other sites I've visited.
Disallowing duplicate posts is a good idea, and for other reasons too.