Here's a variation that doesn't worry about offsets at all, but goes after the target words or phrases themselves.

c:\@Work\Perl\monks>perl -wMstrict -MData::Dump -le
"my @tags = (
   'consisting of: cat1: id1: 7: 20',
   'discouraged: cat1: id2: 39: 50',
   'most cases: cat2: id3: 59: 69',
   );
 ;;
 my %targets;
 ;;
 for my $tag (@tags) {
   my ($string, $cat, $id) = split /:\s+/, $tag;
   $targets{$string} = [ $cat, $id ];
   }
 ;;
 my ($rx_target) =
   map  qr{ \b (?: $_) \b }xms,
   join ' | ',
   map  quotemeta,
   reverse sort
   keys %targets
   ;
 ;;
 my $string = 'Titles consisting of a single word are discouraged, '
            . 'and in most cases are disallowed outright.'
            ;
 print qq{'$string'};
 ;;
 $string =~
   s{ ($rx_target) }
    {($targets{$1}[0]: $targets{$1}[1])$1($targets{$1}[0])}xmsg;
 print qq{'$string'};
"
'Titles consisting of a single word are discouraged, and in most cases
+ are disallowed outright.'
'Titles (cat1: id1)consisting of(cat1) a single word are (cat1: id2)di
+scouraged(cat1), and in (cat2: id3)most cases(cat2) are disallowed ou
+tright.'
[download]

Some important caveats:

• A target phrase like "most cases" does not match with a "most  cases" or "most\ncases" source substring because the target requires an exact match with a single space and the given substrings, while similar, are not exactly equal variations. This can be dealt with fairly easily if file-slurp processing of the source text is used. However, file slurping does not scale well to large (say, more than a few hundred megabyte) files.
• If the "most\ncases" case above is encountered in line-by-line processing of source text (which does scale to enormous files), handling becomes more tricky, but can still be done.
• Update: This approach does not handle nested tags.

Update: In almost every case, use of the full-featured Text::CSV module is preferable to the naive use of split that I have in my example code.