Ok, have made some error output improvements for next nightly release for reCaptcha usage. Not sure where it's failing, but this should help find what exactly is going wrong.
It's possible they're taking too long to complete registration, they complete captcha, and before it's verified it expired. reCaptcha doesn't work so great for long forms as it only lasts about 2 minutes I believe. This issue also works in reverse. They complete the captcha, take too long completing the form, and the captcha session expires. It appears to be a commonly reported problem depending on the usage.
It maybe possible to force the captcha to reset using API as there is a callback event for expiry in reCaptcha API. Have added a bug ticket to monitor this issue further and see if I can track down a cause. If an error is thrown during your tests please let me know what it is so can further track down what's going on.
forge.joomlapolis.com/issues/5858