Fight automated registration

I’m using WP-Gatekeeper (a challenge-plugin) and SK2 against comment spam and it works fine. But i’ve noticed some automated account registrations last time and would like to prevent them (before they are created). So i’d like to have a solution like a challenge or moderation (before a new user-id is fix). I would take (but not prefer) a capcha soluition. i’ve problems in solving captchas myself – but if nothing else exists…
Anyone suggestions?