I had faced the issue of these spam customers on our store too. The store was on magento 1.x . I could not say that a single solution will work 100% as it depends on how the attack has been implemented. Let me share some of my thoughts.
1. Implement google recaptcha
You are going in the right direction of implementing the google recaptcha. This could prevent the case if it is the default vulnerability. I am not sure which version of Magento you are using but here is a quick tutorial of implementing the google recaptcha for magento 1
You can also implement the custom code for recaptcha implementation. Please confirm what you have implemented does the both frontend and server side validation. For me doing the clientside as well as server side validation worked and the spam customer was prevented.
But if you still seeing this issue after implementing the google recaptcha see check point 2.
2. Look for customization and loop holes
Yes if google recaptcha doesn't prevent the issue. There could be a case where any custom extension has the loop hole which may have the code that creates the customer and not well sanitized like form key validation and all. Look for that too.
3. Try implementing honeypot
If these customers are created by submitting the customer registration form with auto fill data, you can add a hidden text field, which normal customer won't see, but these scripts will fill it and then you can check on your controller if value presents in that field. If yes, prevent the customer addition else create the customer. This is my version of the implementation. I think there are other better approaches too.
Hope this will help you solve your issue.