Why not add a "status" field to your form? It doesn't have to show on the form, just be in the main data source. It can default to New. Then, the first time a user submits a form, in the submit rules, set it to Submitted (or whatever, just change it). Then your validation rules can be exactly what they are with the addition of "FormStatus is equal to New".
Hilary Stoupa