It's not a wp_mail issue as the admin notification is sent and if I create a new profile from the Users section of the WP admin, it sends the emails to the new user fine.
Actually, it may or may not be wp_mail issue. The fact that it sends the two emails when you have disabled reCAPTCHA is probably coincidental, as the sending of email on a successful registration and displaying/validating reCAPTCHA are not related.
Also, "sent" does not equate to "received" when troubleshooting email issues. Even if wp_mail sends a message, it could get stopped by your host or the receiving host before it ever gets to the inbox. And just because one particular email goes through ok does not mean that others will. There are a number of possible reasons for that.
The first thing you need to know is if your host throttles emails. When you have a new registration with admin notification, two emails are sent at the same time. Some hosts might throttle this.
I would suggest also filtering the "from" headers and use an address that your host recognizes as valid (i.e. it comes from the same domain). There is a filter hook for that.
I have a general post here with information regarding troubleshooting wp_mail, some things you can do to make your sending more reliable, and also how to set up SMTP (which is the best thing you can do).