I can suggest some different method
This will ensure that <image> is NOT embeded into any <story> tag.

use strict;
my $str = "<story>
                <page>
                        <description> desc </description>
                        <story>aaaaaaaaa</story>
                        <image> notExpected.jpg </image>
                        <headline> head </headline>
                </page>
        </story>
        <story>aaaaaaaaaaaa

<image> notExpected.jpg </image>

aa</story>
        <image>correctImage.jpg</image> ";

while ($str =~ m/<image>(.*?)<\/image>/gs)
{
        my ($image_content) = ($1);
        my $story_st=0;
        my $story_en=0;
        my $prelines = $`;
        while ($prelines =~ m/<story>/gs){$story_st++}   
        while ($prelines =~ m/<\/story>/gs){$story_en++}
        print $image_content, "\n" if ($story_st == $story_en);       
}
[download]