Thanks for pointing out the error in my ‘fixed’ code!

$sentence =~ s/(^| )($phrases_re)( |$)/$1#$2#$3/g for 0, 1;

I wanted to point out a non-error in your correction above, since it took me a minute to understand what its purpose was: If you just did the global replacement without the for modifier, then you'd have the same problem that Crackers2 pointed out with my original, that overlapping matches wouldn't be handled (because the leading space of the trailing match would already have been gobbled up by the trailing space of the leading space). If I'm understanding correctly, then the for 0, 1 is just making another pass to pick up any matches that we missed this way.