So, it looks like the right format is ISO 8601 / RFC 3339.
An example: 1982-07-08 00:00:00.
The official Kassa Compleet extension for Magento 1.x uses the magic Mage_Sales_Model_Order::getCustomerDob()
method:
It returns a value in a format like in my example above.