When a Nintex Workflow is in the state of 'Failed on Start', no workflow notification is sent.
In the context of 'Failed on Start' workflows, there is no workaround to forcing Nintex Workflow notifications to be sent.
Note that 'Failed on start' and 'Failed to Start' are different errors and have different consequences. The primary difference is that 'Failed to Start' is a failure after the workflow starts, although it tends to be immediate. 'Failed on Start' is a failure before the workflow instance starts; the workflow instance doesn't necessarily 'exist' yet and can not be found in Nintex Workflow databases or the Nintex Workflow History List(s). Since Nintex Workflow has no record or awareness of an instance that is 'Failed on Start', it has no way to report its failure.
Workflow Error Notifications are dependent on entries in the Nintex Workflow History List. The "WorkflowHistoryEventReciever" captures 'error' entries in history lists and sends error notifications based off of those entries. The absence of such entries results in no error notification being sent.