Out of curiosity: I may be missing something obvious, but why sort reverse? Why map where a grep would be most suited? (Or better, a for loop with an immediate return on a match?

This was intended to be a joke to the OP, wasn't it?

If I really were to reimplement exists (along the lines of the proposed sub), I'd probably do something like this:

sub my_exists (\%$) {
    my($h,$k)=@_;
    $_ eq $k and return $_ for keys %$h;
    undef;
}
[download]

Update: I saw your update, and yes, it was a joke... how stupid of me to have even the slightest doubt about it!! But your second proposal should be called "exists_ggm" instead... ;-)