Hmmm i remember sitting for hours trying to get around this, which turned out to be easy in the end.
System -> Configuration -> General and click on
Locale Options. Change the
Locale to English (United States)
I retract the above (speed reading). Ok so, if your locale is set to the above, the default date format will be MMDDYY. However, some third party modules may set the date format to a specific format within the module before the resource is saved. Can you confirm you have any third party modules which interacts with Mage_Customer?