Are they not getting the email entirely or is it going to spam? Test with a GMail account if it's just GMail users. You may have landed on a blacklist or your mail server is not setup correctly with DKIM. Sometimes it's just due to the email appearing too spammy. Be sure you've replaced the default registration emails under CB > Configuration > Registration with something more personalized to your site.

1. Is the email sending done by what is set in Joomla Configuration? It's currently set at PHP Mail

CB doesn't have its own mailer API. It's entirely being sent by Joomla.

2. Are there logs to check if emails have gone out? OR is this at the server level

We don't log outbound emails except those sent by CBSubs Mailer.

3. Is there a way to use a 3rd part sender like Sendgrid or similar to mitigate email from being flagged as spam?

If it works with Joomla and extends Joomla's mailer API properly then it should work, but can't guarantee it will.

Make sure your outbound email address matches the domain of your mail server. Specifically all From Address parameters should match the same domain otherwise they'll be considered an alias address which GMail will often bounce. Aside from that you'd need to contact your host and see if they can review outbound email logs (if they have any) and see if there's anything that might be wrong with the email or try contacting GMail support.