We found that the root issue is that older versions of php would silently ignore undefined constants. Php 5.3 enforces this as undefined constants should not be used. Furthermore, since php 5.3, constants can only be defined using the define() function.
PHP_DATE_TIME_FORMAT is specific to OS Commerce and any derivatives (including zen cart). So, unfortunately, it is not something that we can set in php.ini.
To use it with php 5.3, add the following line to the includes/languages/your_template/english.php. Using php 5.2 simply ignores the problem of the undefined constant.
// look in your $PATH_LOCALE/locale directory for available locales..
define('DATE_FORMAT_SHORT', '%m/%d/%Y'); // this is used for strftime()
define('DATE_FORMAT_LONG', '%A %d %B, %Y'); // this is used for strftime()
define('DATE_FORMAT', 'm/d/Y'); // this is used for date()
define('DATE_TIME_FORMAT', DATE_FORMAT_SHORT . ' %H:%M:%S');
define('PHP_DATE_TIME_FORMAT', 'd/m/Y H:i:s');