I have understood that using regex for this problem is not the preferred method, at all. It was however my intention to learn more about regexp, so for now, with your help I have come up with (using the backwards strategy)

# First match !
    $data =~ s|^(.*<section1>.*<rstate>).+(</rstate>.*</section1>.*)$|
+$1$newrstate$2|s;

# Second match!
    $data =~ s|^(.*<section2>.*<rstate>).+(</rstate>.*</subsection>.*<
+/subsection>.*</subsection>.*</section2>.*)$|$1$newrstate$2|s;

# Third match!
    $data =~ s|^(.*<section3>.*<rstate>).+(</rstate>.*</section3>.*)$|
+$1$newrstate$2|s;
[download]

Curious as I am, I will read up on the XML parser and try it as well to see how it compares. Thanks for the help!