If @reqs contains simple string to match the complete line rather than regexes or partial matches, the you could create a hash and do a fast lookup.

%reqs; @reqs{ @reqs } = ();

for( @lines ) {
    if( /^\*R/ && $_ !~ /BADSTRING/ && exists $reqs{ $_ } ) {
        # do something
    }
}
[download]

Lots of ifs, but much quicker when they are true.