It's a little hard to see the problem because I don't know your system, but here are a few things to try:

• Manually check for the file's existence with -e. For example:
  warn "No such path: $x\n" unless -e $x
  This would be placed before the unlink line.
• This seems to be a CGI script. CGI processes run as the web server's user, which is typically nobody. Can nobody see these files and delete them? su - nobody to check this.
• You code doesn't grep through the actual files, but instead looks through one data file. The mistake may be that the paths in that file are fubar.
• There's no need to read in FTS file. This is a waste of memory. Also your search terms don't change, so you can be a little trickier with the regex. Consider something like this:
  

  my $pattern = join '|', map{"\Q$_\E"}@search_terms; 
  while(my $suspect = <FTS>){
     chomp($suspect);
     if( $suspect =~ /$pattern/o ){
        push @delete_me, "$base_path$term";
     }
  }
  [download]

  This creates an regex pattern that is an alternation of all your search terms, each of which has potential regex meta characters escaped. Of course, this may not be want you want if the search terms are regex patterns themselves. In that case, remove the map clause.
• It strikes me as odd that your search terms appear to be filenames. This is intentional?
• If you're going to use $_, enjoy the saved characters:
  

  foreach (@file_list){ # don't bother putting $_ here
    print $_, '<br>';
  }
  [download]

Hopefully in some of this message, you'll find the key to unlocking this thorny problem. Good luck!

--jjohn