You tend to do it a bit like this (untested code, etc):

foreach my $curr_key ( keys %my_hash) {
foreach my $test_key ( keys %my_hash) {
if ( $curr_key eq $test_key ) { do_something();} else
foreach my $elem ( @{$my_hash{$test_key}}){
if ( $elem eq $curr_key ) { do_something();}
[download]

Update: You could also use the CPAN module Quantum::Superposition to do your searches through arrays. It lets you express your queries in more math-set-theory ways.