During my last project I had a problem with the automatic mail system of Drupal 6. One example was the confirmation mail of the system after the registration of the user. The mail was send in English although the user had selected German as default language.

The problem were the variables for the mail section that had not been available in the system. The solution was to add the specific variables to the

/sites/default/settings.php

and translating the mails into the available languages.

Add the following variables into your settings.php file:

$conf['i18n_variables'] = array(
  // User email variables
  'user_mail_password_reset_body',
  'user_mail_password_reset_subject',
  'user_mail_register_admin_created_body',
  'user_mail_register_admin_created_subject',
  'user_mail_register_no_approval_required_body',
  'user_mail_register_no_approval_required_subject',
  'user_mail_register_pending_approval_body',
  'user_mail_register_pending_approval_subject',
  'user_mail_status_activated_body',
  'user_mail_status_activated_subject',
  'user_mail_status_blocked_body',
  'user_mail_status_blocked_subject',
  'user_mail_status_deleted_body',
  'user_mail_status_deleted_subject',
  'user_picture_guidelines',
  'user_registration_help',
);

After storing the settings.php, you have to call the admin/user/settings page in the different languages of your system and translate the texts of the single mails.

Works fine for me.