So, date format is controlled by a particular user's web client's regional settings. I have not had the oppertunity to test this, but if you create a special user with the appropriate regional settings, and make that user the "service" user for a copy of your existing workflow (configurable in the start activity), I think that should generate the dates in the proper format.
This particular method will of course require a way to differentiate between customers in different regions to prevent multiple workflows being triggered by the same document.
Edit: This doesn't work as I thought it might, unfortunately; however, Phil's response below will certainly format it in the manner you are looking for.
Software Support Specialist
Support Team GREEN - Americas