Your last idea is by far the best solution. In fact the order in which you present the different techniques is exactly the progression taken by most people learning Perl (the trade off tends to be different for other languages). The equivalent of your nested loop using hashes is:

for my $element (@array) {
   next if ! exists $lookup{$element};
   # Do the work here
}
[download]

Although grep code often looks nice and clean (or at least compact), it is a nested loop and has the same trouble with performance when the arrays are large as the explicit nested loop you presented as a first try.

btw, even for sample code don't use $a and $b - they are special variables used by sort. Unless you are golfing or writing obfuscated code avoid bed habits, especially when trying to teach someone else good habits. ;)