My personal solution would be to reverse the hash so the original values are keys, but the resultant values for each key would be an array reference so that the lookup would return all appropriate original keys.

Update: Some code

my %original_hash = ( first  => 'alpha',
              second => 'beta',
              prime  => 'alpha', );

foreach $key (keys %original_hash)
{
    push @{$reverse_hash{$original_hash{$key}}}, $key;
}

foreach $rkey (keys %reverse_hash)
{
    print "$rkey = ".(join ', ', @{$reverse_hash{$rkey}})."\n";
}

print "\n";
my %test_hash = reverse %original_hash;

foreach $tkey (keys %test_hash)
{
    print "$tkey = $test_hash{$tkey}\n";
}
[download]

Just a little demonstration loop at the end.

Update' I managed to reproduce the solution in the Cookbook without checking it first. First off, I'm happy about doing such. Second, I figured I'd go ahead and attribute it as such a solution, even though I didn't look ahead of time.

ALL HAIL BRAK!!!