Adding a couple more tests to your script gives us a clue:

@keys = qw(one two five);
unshift @keys,'four';
print "@keys\n";
if (@hash{@keys}) {
    print "yep\n";
} else {
    print "nope\n";
}
 
@keys = qw(one two five);
push @keys, 'two';
print "@keys\n";
if (@hash{@keys}) {
    print "yep\n";
} else {
    print "nope\n";
}
[download]

Gives the result:

four one two five
yep
one two five two
nope
[download]

It would appear that only the presence of the last key in the array is affecting whether the test returns true or false.

I would suggest a possible solution would be to abuse grep, thus:

if ( grep{ exists( $hash{$_} ) } @keys ) { 
    print "yep\n";
} else {
    print "nope\n";
}
[download]