Just like Perl is free to store numbers in the format of its choice (IV, UV, NV, PV), Perl is free to store strings in the format of its choice (UTF8=0, UTF8=1). It's also it's free to change the storage format used at any time, but that's not what's happening here. Consider the following snippet

use utf8;

utf8::upgrade(   my $key_u = "clé" );
utf8::downgrade( my $key_d = "clé" );

my %hash;
++$hash{$key_u};
++$hash{$key_d};

my ($key) = keys(%hash);
[download]

As this shows, keys is perfectly justified in returning the string in any format. If your code assigns semantics to the UTF8 flag, it's buggy. (It is said "to suffer from The Unicode Bug".)