Hello upioneer - this data isn't handled with cookies, it's persistent data that is flowing along the lines of your workflow. One simple way to prevent this is to move from the "start over" form to the "initial form" without using any lines. Use a "Hanging Path Trigger by Path" and configure it to catch the "Start Over" path you're using.
A better way, however, is to utilize the Initialize Data component. Typically all your variables should be declared/created in a component such as the Initialize Data component anyway, and by looping back around to this component at the "Start Over" point, the variable values will be reset as expected.
Another option is to use the "Restart Dialog at End" on the Publishing tab, but this will always restart the dialog when the workflow process ends.
There are lots of options; let me know if none of these work for you and why they don't work, and I'm sure we can find another way for you.