It's the same API for sending emails from forgot login as it is for mass mailer and any email within CB. Have they checked their spam folder to see if it went to spam? I've retested forgot login and appears working fine on all my test installs.

Check with your host and have them review mail server logs and see why it's failing. CB isn't reporting any mailer errors based off the message displayed to the user so it'd have to be blocked in the mail server for whatever reason.

Question: We use Google email through MX records. Do emails from CB go through that or through a different way because it is on the website?

They go through whatever settings you've set in Joomlas global configuration for your mail server. If you're using a Joomla plugin to send emails by other means then that will not work with CB.

Our hosting provider is saying that they have no way of tracking (or seeing errors) on emails because it doesn't go through their servers.

Your host is correct and won't be able to help you in that regard then.

When we go into CB and directly email a user, it works perfectly fine. It is only through the Registration and Password Recovery sections of CB that we aren't seeing any outgoing emails being received.

That doesn't really make any sense as all CB emails send through exactly the same API. It's likely that something about those emails is being specifically blocked by your mail server. Try changing the subject and body of the registration emails within CB > Configuration > Registration. Also ensure the From Address on that same tab is valid and from your mail server domain.