Isn't a double-level of interpolation and eval required?

perl -wMstrict -e
"my $regexSearch  = $ARGV[0];
 my $regexReplace = $ARGV[1];
 my @strings = qw(103_foo 124_bar 109_quux);
 for my $string (@strings) {
   my $oldstring = $string;
   $string =~ s{ $regexSearch }{ qq{qq{$regexReplace}} }xmsee;
   print \"renamed $oldstring to $string \n\";
   }
"
1(\d\d.*)   4$1
renamed 103_foo to 403_foo
renamed 124_bar to 424_bar
renamed 109_quux to 409_quux
[download]

Update: See also printig with variables in text and simple regular expression for further discussion.