Here's a non-recursive way which I think fits your criteria:

use strict;
use warnings;
use Test::More;

my $wiki =
    '_/one *two*/ three_ null _/four *five*/ six_  null _/seven *eight
+*/ nine_';

my $expected =
    '<u><i>one <b>two</b></i> three</u> null <u><i>four <b>five</b></i
+> six</u>  null <u><i>seven <b>eight</b></i> nine</u>';

my %h = (
    '*' => 'b' ,
    '/' => 'i' ,
    '_' => 'u' ,
);

my $DBG = 1;

sub flip {
    my $s = shift;
    my $z = $h{$s};
    $h{$s} = $z =~ /\// ? substr ($z, 1, 1) : "/$z";
    return "<$z>";
}

sub tf {
    diag "Pre: '$_'\n\n" if $DBG;
    s{([_*/])}{flip($1)}eg
};

$_ = $wiki;
diag "IN <= '$wiki'\n\n" if $DBG;
tf();

is ($_, $expected, " repeated replace works");

done_testing;
[download]