And I got it. What was missing was re-loading the text domain for WooCommerce, that was loaded with the current locale at initialization:
// set the current locale and send email with it active
unload_textdomain('woocommerce');
setlocale(LC_ALL, $new_locale);
global $q_config, $locale, $woocommerce;
$locale = $new_locale;
$q_config['language'] = substr($new_locale, 0, 2);
$woocommerce->load_plugin_textdomain();
global $wc_cle_wc_email;
$wc_cle_wc_email->customer_completed_order($order_id);
// set the old locale back
unload_textdomain('woocommerce');
$q_config['language'] = substr($old_locale, 0, 2);
$locale = $old_locale;
setlocale(LC_ALL, $old_locale);
$woocommerce->load_plugin_textdomain();
Some of the calls setting the locale variables are probably redundant and/or simply unnecessary, but this works.