The easiest approach I would have to offer is to just let it run but have it check if a record exists in the list before creating a new item. If exists, email the user that their submission was not received, as they already created one on XX/XX/XXXX and to contact XXX for further assistance. 

Unless Nintex can offer a better suggestion. I would of suggested the get tasks action, however you don’t have many filtering options other than status, start date and end dates. Also you cannot search across all instances for one workflow, only one specific workflow instance. :(
 

You can also use this option possibly:

An alternative is to store the initiator email in the list in a text field. Use a data source to fetch the record that matches the current user email against that field. If it returns a record (a match) then disable the form by using a validation rule where they cannot submit if a match is returned and maybe a label pops up saying “our records indicate you have already submitted blah blah blah ….”

I ended up capturing the submitter’s email into a Nintex table and created a Submit rule to see if the current user was found in the table. If so, they would get a validation error on the form letting them know they had submitted the form previously.