Another one of those crazy days today where I got stuck with this awful issue. I had a Nintex workflow on a SharePoint document library. The document library was set up to receive incoming emails. The workflow must kick off when the item is created in the document library triggered by the incoming email.
The problem was that the workflow was not starting. If I uploaded a document into the document library manually, the workflow would then successfully kick off.
Ensure that the worklow is saved and published with a site collection owner other than SharePoint\System.
The following stsadm command must also be run:
stsadm -o setproperty -pn declarativeworkflowautostartonemailenabled -pv true
This will ensure that the workflow is created by the account that created the item(sender of email in my case).