I had similar problem with other transactional emails, and to address these often not clear issues I recommend you install WP MAIL SMTP plugin.
This has a detailed log of sent mails, and in case there are errors also detailed information about what happened.
With it I could prove to my hosting provider that the mails bounced on his SMTP server – as per policy, there was 100/hour limit.
As we sometimes had peak hours with more that 100/hour, we ran into this issue.
After explaining the situation to support, and proving it’s transaction mails, and not some spam, the settings were changed to Per Day and not Per Hour.
Since then, all is great 🙂
(hosting with dreamhost)