Ubercart

Okay, with some more investigation:
Between Drupal, Ubercart and Paypal, all systems seem to be using UTF-8 as a standard.

Looking at the customers' original problem email, the source code shows a different text encoding. So it may simply be an email client issue, where the email software they're using can't deal with UTF-8 or is setup to not use UTF-8 by default.

I'll double check this.

As a half-solution I ended up modifying the Paypal module.

Instead of just feeding in the items in the Paypal variable 'DESC', I also appended the site name and order #.

So instead of this in the Paypal email:
"Item/Product Name: 1× Info-impôts – Offre groupée d’out"

I now see this:
"Item/Product Name: Website Name - Order # XXX - 1× Inf"

So this works well for us because the customer can still identify what the transaction was for, even if there's accent characters in the product title.

To do this I used something like the following, in the paypal module file:
$desc = variable_get('site_name', $_SERVER['SERVER_NAME']) . " - " . "Order # " . $order->order_id . " - " . $desc;