Mark, have you also tried BadBehavior2 plugin? It keeps away spam bots.
Yes, I also had BadBehavior2 installed, I would still get several bad new users each day or so. Now when I say bad user, nothing ever got posted by these "users", They would register, never log in, then we'd delete them. They were judged "bad" based on the user name and/or email address entered, plus never logging in.
Now I never looked into it, but I kinda of assumed BadBehavior was at least in part behind why they never came back. The captcha plugin just helps keep them out in the first place. I only have it turned on to register new users, making any kind of post on our site requires you to be logged in. And even then it still has to be approved.
Just to give you an idea, we have about 50 users (small site), the most recent user who registered this month is number 323. Between users 194 and 314 there was only 1 valid user ID. Between 314 and 323 I've only deleted 1 user, although I see one that should most likely go. I don't know, user name is
93bi91biba21. Think they're valid?
~Mark