Here is a FIFO approach:

my @lastmatches;
my $keep = 5;
while ( my $line = <FILEHANDLE> ) {
    next unless $line =~ /criteria/;
    push @lastmatches, $line;
    unshift @lastmatches if --$keep < 1;
}
[download]

I don't know if unshift is "expensive" from a time-critical standpoint, but where the array is never more than five elements long, it probably isn't terribly efficient to use it in this way. I've essentially created a fifo list that won't grow to larger than five elements. It does scale pretty well though, and passed my tests.

Or there's this grep and list slice approach:

my @lastfive = ( grep { /criteria/ } <FILEHANDLE> ) [ -5 .. -1 ];
[download]

UPDATE: I created a 5mb file and used the grep method along with a list slice to gather the last five using the following snippet. On the machine I tested it with, it took about 5 seconds to grep the file using a simple regex. ... that on an old beat up 266mhz Pentium II notebook. Again, I'm not sure how time critical the OP's needs are, and while I know the grep method is slower than the File::ReadBackwards method, it's pretty simple, and seems to work just fine as long as it's ok to take a few seconds per 5mb file. Here's the test snippet:

use strict;
use warnings;

# Create the 5mb file.
my @alphabet = ( "A".."Z", "a".."z", " ", "\n");
open OUTFILE, ">file.txt" or die;
print OUTFILE $alphabet[ rand( @alphabet) ] for 1 .. (1024 * 1024 * 5)
+;
close OUTFILE;

# Find the last five occurrences of 'abc'.
print "Testing grep method:\n";
open IN, "file.txt" or die;
my @lastfive = ( grep { /abc/ } <IN> ) [-5 .. -1];
close IN;
my $count = 5;
print $count--, ".: ", $_ foreach @lastfive;
[download]