At one point or another I tried everything. What's worked is a combination for me:
1. Answer question correctly to register, or use the Contact Us form (the questions are easy, but chosen at random).
2. All links are "nofollowed", unless I manually enter them into a white list.
3. New posters cannot include links in their posts or signature until they enter a category of "confirmed member". It is set at 10 posts. Few third-world human-spam-bot has the patience to wait, plus they don't know if/when they'll be able to post links.
4. Email confirmation is required to register. Meaning people have to have a working email address to post in our site.
5. I check new registrations every day and double check if I see anything suspicious.
That has stopped almost all spam. There are still people willing to stick around long enough until they can post links and spam the site. They are few and far between, so it's easy to deal with them.
It's incredible how far people these people are willing to go to spam.