I played around with your code (well, actually I used Stephens's code for simplicity) and found a solution that amazed me: If you add 'o' to the regex operators (making it '/ego') everything works as expected. Here's my code:

#!/usr/bin/perl -w

use strict;

print doFunc("MAIN", "B(1)+C(2)") . "\n";

sub doFunc
{
        my ($theFunc, $rem) = @_;

        my $re = &get_re($rem);
        
        $rem =~ s/(\w+)\(($re)\)/&doFunc($1,$2)/eog;

        return "func $theFunc returns <$rem>";
        
}

##      
### When we're called with the initial
### state, return "1|2". Otherwise, return
### our input, quotemeta'd.
###     
sub get_re
{
        my ($in) = @_;

        if ($in eq "B(1)+C(2)")
        {
                return '1|2';
        }
        else
        {
                return quotemeta ($in);
        }
}

exit (0);
[download]

Sorry that I can't tell you why perl is behaving like this. '/o' shouldn't change the behavior at all (at least that's what I though) and $re doesn't change either.. Maybe perl messes up the namespaces when doing recursive calls using a regex? I really don't know..

By the way: When I'm not using the '/o' operator and trying to print to STDERR just before the regex is executed my perl (5.6.1, linux 2.4.2) coredumps on me..

Regards, -octo-