i like QM's solution .. though I have to also question OP w/why store your data in 2 arrays?

Hashing (be aware of uniqueness and sorting issues) is one option:

my %hash;
@hash{ @array1 } = @array2;
my @array1 = grep( ! /foo/, keys %hash );
my @array2 = map { $hash{$_} } @array1;
[download]

Or even better/more robust, build a different data structure:

my @array = grep
    $_->[0] !~ /someRE/,
      map { [ $array1[$_], $array2[$_] ] }
        0 .. $#array1;
@array1 = map { $_->[0] } @array;
@array2 = map { $_->[1] } @array;
[download]