foreach my $key (
   map  {$_->[0]}
   sort {$b-[1] <=> $a->[1]}
   map  {[$_, $_ eq q{Foo}]}
   keys %hash;
{
    # Do something here
}
[download]

Cheers,

JohnGG

Update: Wrote a test script to see if things worked as I expected.

use strict;
use warnings;

# Set up hash with prominent marker key/value pairs
# and a load of fillers. No 'Foo' yet.
#
my %hash = (
   Bib => 387,
   Bob => 745,
   Baz  => 106);
$hash{$_} = int rand 10
   for q{Bea} .. q{Bep};

my @keysOrder = ();
my @prefOrder = ();
my $key;

# Push key and value strings onto array in keys order.
#
foreach $key (keys %hash)
{
    push @keysOrder, qq{$key => $hash{$key}};
}

# Push key and value strings onto another array in
# preferred order.
#
foreach my $key (prefOrder(keys %hash))
{
    push @prefOrder, qq{$key => $hash{$key}};
}

# Print results side by side for comparison.
#
print qq{\nKey Order     Preferred Order\n};
for (0 .. $#keysOrder)
{
    printf qq{%-14s%-14s\n}, $keysOrder[$_], $prefOrder[$_];
}

# Add 'Foo' to the hash and repeat test.
#
$hash{Foo} = 999;
@keysOrder = ();
@prefOrder = ();

foreach $key (keys %hash)
{
    push @keysOrder, qq{$key => $hash{$key}};
}

foreach my $key (prefOrder(keys %hash))
{
    push @prefOrder, qq{$key => $hash{$key}};
}

print qq{\nKey Order     Preferred Order\n};
for (0 .. $#keysOrder)
{
    printf qq{%-14s%-14s\n}, $keysOrder[$_], $prefOrder[$_];
}

sub prefOrder
{
    return
       map  {$_->[0]}
       sort {$b->[1] <=> $a->[1]}
       map  {[$_, $_ eq q{Foo}]}
       @_;
}
[download]

Here is the output.

Key Order     Preferred Order
Ben => 8      Ben => 8      
Bed => 2      Bed => 2      
Bec => 5      Bec => 5      
Bei => 8      Bei => 8      
Bej => 3      Bej => 3      
Bek => 0      Bek => 0      
Beh => 4      Beh => 4      
Bib => 387    Bib => 387    
Bea => 1      Bea => 1      
Bep => 9      Bep => 9      
Baz => 106    Baz => 106    
Bee => 2      Bee => 2      
Bem => 4      Bem => 4      
Bef => 3      Bef => 3      
Bob => 745    Bob => 745    
Beg => 6      Beg => 6      
Beb => 8      Beb => 8      
Bel => 2      Bel => 2      
Beo => 7      Beo => 7      

Key Order     Preferred Order
Ben => 8      Foo => 999    
Bed => 2      Ben => 8      
Bec => 5      Bed => 2      
Bei => 8      Bec => 5      
Bej => 3      Bei => 8      
Bek => 0      Bej => 3      
Beh => 4      Bek => 0      
Bib => 387    Beh => 4      
Bea => 1      Bib => 387    
Bep => 9      Bea => 1      
Baz => 106    Bep => 9      
Bee => 2      Baz => 106    
Bem => 4      Bee => 2      
Bef => 3      Bem => 4      
Foo => 999    Bef => 3      
Bob => 745    Bob => 745    
Beg => 6      Beg => 6      
Beb => 8      Beb => 8      
Bel => 2      Bel => 2      
Beo => 7      Beo => 7
[download]