My current fix...

I fixed this by calling a new theme hook in the Drupal core (in the date formatting function), then implementing it in my themes. This is giving code like:

function phptemplate_date_format($type, $format) {
$language = 'en';
if (function_exists('i18n_get_lang')) {
$language = i18n_get_lang();
}
switch ($language) {
case 'fr':
switch ($type) {
case 'custom':
switch ($format) {
case 'F dS':
$format = 'd F'; break;
}
break;
default:
switch ($format) {
case "F j, Y - H:i":
$format = "j F Y - H\hi";
}
}
break;
}
return $format;
}

As well, this new hook should be implemented in core officially.