If I understand the task correctly, I think you'll be better off nesting the loops this way (not tested):

# build the list of targets

my @targets = map { /^A(\d+)/; $1 } @orthologs;

# go through @pids and segregate them into @hits and @potentials

my @hits = my @potentials = ();

for my $p ( @pids ) {
    my $itsahit = 0
    for my $t ( @targets ) {
        if ( $p =~ /$t/ ) {
            push @hits, $t;
            $itsahit++;
            last;
        }
    }
    push @potentials, $p unless ( $itsahit );
}
[download]