Rather than using a pure regex solution, you can find all of the starting offsets of pattern1 and pattern2 and then use List::Util::first (along with reverse) to find which pairs of pattern1 bracket each pattern2. Once you have that you can use substr to replace the text working from the end of the string backwards so the offsets aren't invalidated as the string changes.

use strict;
use warnings;

use List::Util q{first};

my $patt1   = q{ABC};
my $patt2   = q{XYZ};
my $replace = q{999999};

my $string  = <<EOD;
kjdfjdfXYZewfkfABClkjfef
sahasjABCsjhksfhABCsjsjfs
oreweouABCkerjeXYZewfkfABClkjfef
xcvmvbbbvABCdjfABCjsdjfsdf
jjnnjfABDjfXYZdjdjABCjfdkjfABClsfj
isosiXYZcsfsjfABChfdhgfABCyeryerXYZffjfs
EOD
print $string, q{-} x 25, qq{\n};

my @patt1Posns = ();
push @patt1Posns, ( pos( $string ) - length $patt1 )
   while $string =~ m{\Q$patt1}g;
my @patt2Posns = ();
push @patt2Posns, ( pos( $string ) - length $patt2 )
   while $string =~ m{\Q$patt2}g;

my @substituteSets = ();
foreach my $patt2Posn ( @patt2Posns )
{
    my $start = first { $_ < $patt2Posn } reverse @patt1Posns
       or next;
    my $end   = first { $_ > $patt2Posn } @patt1Posns
       or next;
    push @substituteSets, [ $start, $end - $start + length $patt1 ];
}

for my $raSubstituteSet ( reverse @substituteSets )
{
    substr
       $string,
       $raSubstituteSet->[ 0 ],
       $raSubstituteSet->[ 1 ],
       $replace;
}

print $string, q{-} x 25, qq{\n};
[download]

This produces

kjdfjdfXYZewfkfABClkjfef
sahasjABCsjhksfhABCsjsjfs
oreweouABCkerjeXYZewfkfABClkjfef
xcvmvbbbvABCdjfABCjsdjfsdf
jjnnjfABDjfXYZdjdjABCjfdkjfABClsfj
isosiXYZcsfsjfABChfdhgfABCyeryerXYZffjfs
-------------------------
kjdfjdfXYZewfkfABClkjfef
sahasjABCsjhksfhABCsjsjfs
oreweou999999lkjfef
xcvmvbbbvABCdjf999999jfdkjf999999hfdhgfABCyeryerXYZffjfs
-------------------------
[download]

I hope this is of use.

Cheers,

JohnGG

Update: Fixed typo. s/and/as/