TMTOWTDI, here is a map solution:

my %remove;
++$remove{$_} foreach @remindexes;
@array = map ((exists $remove{$_} ? () : $array[$_]), 0..$#array);
[download]

Basically build up a hash lookup for what you don't want, and map the indexes of the array into nothing or the array element as desired.

BTW recent conversations with tye have reminded me that entering and leaving blocks has a significant overhead. Therefore I have not written this map with a block.