To start a workflow it is required some minimum permissions.

Minimum Permissions for Nintex Workflow for Office 365 

Anonymous users can submit a form which means they have contribute permissions. So this requirement is met. How can I make sure the workflow is started when they submit the form? 

I have marked yours correct, however it wasn't the full answer. Of course you have to have a certain permission. But the answer is actually anonymous users cannot start workflows. 

So to work around this I had to create a site workflow that collected unprocessed items and then start the workflow on these items.

This works like a champ.