The first thing you should do is to get the close() calls in the right context...

#!/usr/bin/perl
use strict;
use warnings;

use File::Find;
my $DIR = "/tmp/logs/";
find(\&queries, $DIR);

sub queries() {
    if ( -f and /^ftr001/ ) {
        print "----------------------------------------------\n";
        print "Searching File:", $_, "\n";
        print "----------------------------------------------\n";
        open(UNZIP, "gunzip -dc < $_ |") or die "gunzip: $!";
        open(RECORDS, "/tmp/logs/records.txt") or die "Could not open 
+records file: $!";
        my @REC=<RECORDS>;
        chomp @REC;
        close RECORDS;

        while ( <UNZIP> ) {
             my $EACH_LINE = $_;
             foreach my $REC_QUERY (@REC) {
                 print "Searching for current record: $REC_QUERY\n";
                 if ( $EACH_LINE =~ /\($REC_QUERY\)/ ) {
                     print "Querying for record: $REC_QUERY\n";
                     print "$EACH_LINE\n";
                 }
             }
        }
        close UNZIP;
     }
 }
[download]

...in that way you'll be closing the files at the right time i.e. after you've finished with them. Otherwise you'll encounter problems...

After that, if I've understood you correctly, the simplest approach would be to convert the sought after records into an RE and use that against each file. Moreover, there's a marked performance hit by opening the records file once for every directory - c/w once at the outset - something along the lines of the following (untested) snippet...

#!/usr/bin/perl
use strict;
use warnings;

use File::Find;
my $DIR = "/tmp/logs/";
find(\&queries, $DIR);

open(RECORDS, "/tmp/logs/records.txt") or die "Could not open records 
+file: $!";
local $/ = undef; # Ignoring binmode as its a text file
my $RE = join '|', <RECORDS>;
close RECORDS;

sub queries() {
    return unless -f and /^ftr001/;
    print "----------------------------------------------\n";
    print "Searching File:", $_, "\n";
    print "----------------------------------------------\n";
    open(UNZIP, "gunzip -dc < $_ |") or die "gunzip: $!";

    while ( <UNZIP> ) {
        next unless /$RE/;
        print $_;
    }
        close UNZIP;
}
[download]