TL;DR

If you are not interested in the details how the translation works, skip the content up to the
What to check if your translation isn't working section below, especially the subsection
Solution for Module Scope Translation conflicts.

Magento Translation Overview

Magento prioritizes translations sources (from highest to lowest):

1. DB (the core_translate table)
2. The theme translate.csv file
3. The app/locale/*/*.csv files

How is the translation array built?

Module Translations

First all files from app/locale/*/*.csv that are referenced from active modules etc/config.xml files are parsed. Here is a walkthrough of the process:
Assume Magento finds the following config.xml section:

<!-- excerpt from Mage/Catalog/etc/config.xml -->
<frontend>
    <translate>
        <modules>
            <Mage_Catalog>
                <files>
                    <default>Mage_Catalog.csv</default>
                </files>
            </Mage_Catalog>
        </modules>
    </translate>
</frontend>

And in that file, the following translation is specified for the locale configured for the current store view:

"AAA","BBB"

Under these circumstances, Magento creates the following records in the translation array:

array(
    "AAA" => "BBB",
    "Mage_Catalog::AAA" => "BBB"
)

The second value is the Module Scope Translation. The prefixed module name is taken from the config XML node containing the translation file declaration.

If the same translation is specified again by a second module file, e.g. in Some_Module.csv the translation is "AAA","CCC", it will NOT OVERWRITE the "AAA" setting. Instead, it will only add a new record with the second module name "Some_Module::AAA" => "CCC".

If the developer mode is enabled, it will even unset the "AAA" record if it finds a second record with the same key in another module translation. This makes it easier to spot module translation conflicts during development.

Theme Translations

Second, the translations loaded from the first translate.csv file in the theme fallback for the current locale simply replace existing records in the translation array.
So continuing the previous example, a translate.csv record "AAA","DDD" would lead to the following translation data:

array(
    "AAA" => "DDD", // This is overwritten by the translate.csv file
    "Mage_Catalog::AAA" => "BBB",
    "Some_Module::AAA" => "CCC"
)

Of course records in the translate.csv with new translation keys are simply added to the array.

Database Translations

Translations from the core_translate table are basically merged into the translation array just like the theme translations.
Existing keys from the module or theme translations are overwritten by database records, new ones are added.

Translation Lookup

When the __() method is called, Magento first looks for a translation in array matching the current module.
The current module is determined by the class name on which the __() class is called. For example, in blocks the responsible method looks like this:

// Excerpt from Mage/Core/Block/Abstract.php
public function getModuleName()
{
    $module = $this->getData('module_name');
    if (is_null($module)) {
        $class = get_class($this);
        $module = substr($class, 0, strpos($class, '_Block'));
        $this->setData('module_name', $module);
    }
    return $module;
}

The methods in Helpers and Controllers work correspondingly.

Example Lookup Scenarios

For an example, lets say $this->__('AAA') is called in a template file. If the associated block has the type Mage_Core_Block_Template, Magento will first check for a Mage_Core::AAA record. If it doesn't find it, it will fall back to the translation for the key AAA.
In the example scenario this will result in the translation DDD (from the translate.csv file).

In a different scenario the associated block could be Mage_Catalog_Block_Product_View. In this case Magento would first check for a translation record Mage_Catalog::AAA, and would find the translation AAA.

So in effect, the module scope translations have a higher priority then any generic translations. Which translation is used depends on which module the class is from calling the __() method.

What to check if your translation isn't working

If your translation from a translate.csv file isn't being used, follow this checklist:

1. Is the translation cache turned off/refreshed? (Solution: clear the cache)
2. Is the translate.csv file really in the theme fallback for the current store? (Solution: fix theme configuration)
3. Is there a conflicting record for the translation in the core_translate table? (Solution: remove the conflicting record from core_translate)
4. If all the previous points aren't the cause, there must be a conflicting translation from a different module. (Solution: see below)

Solution for Module Scope Translation conflicts

If you find the final case is true, simply add the translation a second time to your translate.csv with the module scope of the module doing the translation.
In the example, if you always wanted AAA to be translated as DDDvia the theme translation, you could do this in your translate.csv:

"AAA","DDD"
"Mage_Catalog::AAA","DDD"
"Some_Module::AAA","DDD"

In practice, I only add the module scope to the translation if there is a conflict, that is, if a translation isn't working.

Additional Notes

Inline Translation

The inline translation feature of Magento also adds the custom translations to the core_translate table using the module scope prefix.

Backward Compatibility

The priority of the theme translations used to be higher then the database translations up to Magento version 1.3 or so.

XML Translation

Magento sometimes evaluate translate=""arguments in config.xml, system.xml and layout XML to translate child node values.
A helper class can be specified in those cases using the module="" argument to specify the module for the translation scope.
If no module argument is specified in the XML, the core/data helper is used to translate the child node values.

Further Information

I confess I glossed over some details of the Magento translation process in this post, but only because I don't want to too much information.

• Some technical details while the translation array is built
• The possibility to use additional translation files for modules
• Store view scope for core_translate records
• Pros and cons using the different methods of translation

Please ask a separate question if more information is required.

The problem comes from a core bug.

See js/varien/js.js around line 450:

...
} else if (!day || !month || !year) {
    error = 'Please enter a valid full date.';
} else {
...

See the problem? It's the period ., which does not appear in the CSV, so the translation is missed every time. The easiest solution is the edit this file directly, removing the period so that translation works again... but of course, modifying core is not best practice.

Long Solution

If you have a generic local code pool module on your system, add or edit its jstranslator.xml file, and add this:

<?xml version="1.0"?>
<jstranslator>
    <!-- js.js -->
    <validate-date-full-date translate="message" module="rootd">
        <message>Please enter a valid full date.</message>
    </validate-date-full-date>
    <!-- end js.js -->
</jstranslator>

Here we should effectively overwrite the entry for this message that was originally defined in app/code/core/Mage/Core/etc/jstranslator.xml, and include the period which core code expects according to js/varien/js.js. Then, you can add an entry to your CSV:

"Please enter a valid date.","Your translation here"