Here's an idea: Add a hidden field to your form called Count (or whatever you want), make it a promoted property so it appears in the library columns, and when you submit a new form to the library make sure the value for Count is set to 0.
Next, add a step to the very top of your workflow to increment the value in the Count column by 1 every time the workflow runs.
Put the rest of your workflow (the steps you already have) underneath this new step inside an If condition: "If Current Item:Count is equal to 1".
Now, the very first time you submit a form to the library, Count will be incremented from 0 to 1, the If condition for the rest of your workflow will be satisfied, and the rest of your workflow will run just the way you want.
If the user deletes the form and then restores it, Count will be incremented from 1 to 2, the If condition will NOT be satisfied, and the rest of your workflow will NOT run.
I haven't actually had a chance to test this, so if you try it do let me know if you run into problems.