I've ran into this before and the issue was my client's IT department messed up their Office 365 email/SMTP settings and accounts. Once they revamped the settings and accounts there was no issue.
If Kentico is sending the emails but they are sporadic then check your SMTP provider. For simplifying things setup a free send grid account and see if the issue persists. If so there are some other web.config keys you can add if you need to turn logging on.