I would suggest not splitting the string into an array (Update: at least not by words), since this kind of matching sounds like it'd be easier to do with two regexes - one for the stop words, and one for the phrases. Have a look at my node Building Regex Alternations Dynamically. Then, I'd suggest you process the input string piece by piece, because that should make your requirement of not replacing stop words inside the longer matches possible - see "Global Matching" in perlretut, and a more complex example of the usage of m/\G.../gc in perlop under "\G assertion".

Update: Here's a solution that takes a simpler route than m/\G.../gc, using split:

use warnings;
use strict;

my %stops = map {$_=>1} qw/ I am the of and /;
my %terms = ( 'manager of sales' => 1 );
my $str = 'I am the senior manager of sales and of marketing';

my ($re_stops) = map {qr/\b(?:$_)\b/i} join '|', map {quotemeta}
    sort { length $b <=> length $a or $a cmp $b } keys %stops;
my ($re_terms) = map {qr/\b(?:$_)\b/i} join '|', map {quotemeta}
    sort { length $b <=> length $a or $a cmp $b } keys %terms;

my @s = split /($re_terms)/, $str;
for my $i (0..$#s) {
    if ($i%2) {
        print "*", $s[$i], "*\n";
    }
    else {
        $s[$i] =~ s/$re_stops//g;
        $s[$i] =~ s/^\s+|\s+$//g;
        print $s[$i], "\n";
    }
}

__END__

senior
*manager of sales*
marketing
[download]

Update 2: Added the case-insenstive matching flag /i to the regexes and fixed a typo in the text.