Issue
When running a workflow that includes a Send an Email action, the workflow will complete successfully, however emails are sent intermittently.
Resolution
Open a support ticket with Microsoft SharePoint support with the Workflow Instance ID of one affected workflow, along with the Start Time and Last Run Time from the Workflow Status page of the instance.
Additional Information
SharePoint Online handles the mail flow for internal emails, as such Nintex does not have any control of email delivery while workflows use the internal mail system of Office 365.