Having had this problem and forgetting what I did to fix it, I did another search to find the answer so posting it here.
The issue is that though workflows publish correctly (i.e. no errors), they still do not fire (not sending email, not logging, etc.). In SharePoint Online, it turns out that a feature that SHOULD be enabled is not.
When this happens to you, navigate to the site where you are adding the workflow, click the Gear then select Site Settings. Find the Site Features (under Site Settings). Scroll to the bottom of the page and find the feature "Workflows can use app permissions" and activate it: