I encountered the same problem trying to translate errors messages. I found that the translation were done in Zend_Form_Decorator_Errors, after that each error message were processed by the function Zend_Validate_Abstract::_createMessage

Zend_Form_Decorator_Errors::render () {

    // ...

        $errors = $element->getMessages();
        if (empty($errors)) {
            return $content;
        }

        if (null !== ($translator = $element->getTranslator())) {
            foreach ($errors as $code => $message) {
                $errors[$code] = $translator->translate($code); // pre-processed messages are deleted here
            }
        }

Maybe that the translator should be passed to each validator to create localized validators

Available as of r7854 (make sure you update both incubator and core). Translations are now possible globally for all validators extending Zend_Validate_Abstract, which affects Zend_Validate, Zend_Form, and Zend_Filter_Input. This change also allows for variable substitution in messages.