$str =~ m/[^<story>]/

That doesn't do what you think it does. What it does, is match "any character that isn't one of '<', 's', 't', 'o', 'r', 'y', '>'". What behaves more like what you're after, is (?!<story>) or (?<!<story>), i.e. negative lookahead or lookbehind. But even that wouldn't work, as it can still match a string containing "<story>", only not at that exact spot.

What I would do, if using a full-blown XML/SGML/HTML parser is deemed unnecessary, is match both the substrings between "story" tags, and other substrings between "image" tags, in that order of matching precedence. And only keep the latter.

Try this on for size:

@images = grep defined, $str =~ m#<story>.*?</story>|<image>(.*?)</ima
+ge>#gs;
[download]

That'll match every correct image. If you're sure you want just one, you still need the /g modifier and the list context, but only keep the first proper match:

my($image) = grep defined, $str =~ m#<story>.*?</story>|<image>(.*?)</
+image>#gs;
[download]