I did a couple of tests but I do not understand what is going on.
There is also an older key of Antoine 231A87628530E205 which encodes
his name in Latin-1 (wrong charset during creation or PGP was used).

Using

  gpg -vvv ....

shows the character set used by gpg. Maybe this gives some insights.
If you know that the command line is UTF-8 you may use the option
--utf-strings to avoid any conversion.

FWIW, gpg uses LC_ALL, LC_LANG, LANG in that order to determine the
locale. Antoine's original report shows

  Locale: LANG=fr_CA.UTF-8, LC_CTYPE=fr_CA.UTF-8 (charmap=UTF-8)

and thus UTF-8 should be used due do LC_CTYPE. gpg converts command
line arguments back and forth as needed but passes them as utf-8 to
the keyserver (which is the reason that the "searching for =..."
message renders it differently.

I think werner means --utf8-strings instead of --utf-strings.

hm, common/utf8conv.c says this:

  /* Note that we silently assume that plain ASCII is actually meant
     as Latin-1.  This makes sense because many Unix system don't have
     their locale set up properly and thus would get annoying error
     messages and we have to handle all the "bug" reports. Latin-1 has
     always been the character set used for 8 bit characters on Unix
     systems. */

I wonder if this is still the best choice. In my experience, far more machines
have text in some UTF-8 encoding today than in Latin-1. this is especially true
for systems that deal with OpenPGP User IDs, where UTF-8 is the canonical
representation.

If the user's environment claims that it's plain ASCII and we're seeing 8-bit
characters, gpg does have to make a decision about what to do. i see four options:

a) report an error and fail.

b) pretend that the 8-bit characters are Latin-1 (this is "OK" because any
bytestring is a valid Latin-1 string)

c) pretend that the 8-bit characters are UTF-8

d) do some sort of autodetection on the bytestring (e.g. if it is a valid UTF-8
byte sequence then treat as UTF-8, otherwise treat as Latin-1)

option (a) is annoying and likely a cause of spurious complaints, as the comment
notes. GnuPG is currently going with option (b). Option (c) seems more
reasonable to me because of OpenPGP's relationship with UTF-8, but introduces
some error cases (what do we do where the bytestring is not valid UTF-8?).
Option (d) avoids error cases but might be a bit more delicate to implement.

What do you think?

i prefer solution (c): we should assume utf8, if we are going to assume anything
at all.

if the user doesn't provide UTF8 *and* doesn't have the proper locale set, then
we should exit with a meaningful message.

that way, things break for people that don't have a properly configured locale
*and* try to input non-UTF8 as opposed to just fail if locale is *not
configured*, which is a pretty common scenario.

Solution (c) will be used for 2.1.8.

Won't fix in 1.4 because that version is mostly useful on old systems and those
don't have proper utf-8 supoort anyway.