You really can't rely on "hash order" for anything, including consistency from run to run. That means that you must ensure that the treatment of non-Foo keys is independent of order.

Your list construction with exists, trinary, and grep looks good to me. That would be my first choice.

Another way would be to construct a sort routine which returns -1 if $a eq 'Foo', 1 if $b eq 'Foo', and zero otherwise. That is likely to be less comprehensible than what you have.

for my $key ( sort {
        $a eq 'Foo' and return -1;
        $b eq 'Foo' and return 1;
        return 0;
    } keys %hash ) {
    # do stuff
}
[download]

That will work fine for hash keys, but may go strange on you if there can be more than one "Foo" in the list.