We use CAPTCHAs, and we also use some "simple" questions that people have to answer (interestingly, I had so many people unable to solve "1 + 1 - 1" that I had to take that one off. Many of them seemed to get "2" or something else as an answer, frighteningly).
The volume of spambots we get has been drastically reduced by the questions, but we always had CAPTCHAs since the forums first existed, so I don't know what the volume of spambots would have been like without those. There was a definite tipping point past which the CAPTCHAs were clearly no longer that effective against at least some spambots, though, and that's when I added those other questions.
Nowadays we're really only seeing a very occasional spam from someone that I suspect is a low-paid actual person hired to come here and do the spam, rather than a bot proper. There's no cure for them other than just deleting their messages and banning them, so far as I know.