That is because the "?" in ".*?" makes the ".*" pattern ungreedy

For example, compare:

$str="taaaaaaaa";
$str=~/(ta+)/; print "$1\n";
$str=~/(ta+?)/; print "$1\n";
[download]

In your case...

$str =~ m/[^<story>].*<image>(.*)<\/image>.*?[^<\/story>]/s;
 ## <- w/o the "?" should work
[download]

citromatik

UPDATE: I apologize for my answer: although my previous comment is correct and my regexp do the work, the concept of the regexp is totally incorrect. It should be expressed as:

$str=~s/\n//g; 
$str =~ m%<story>.*</story><image>(.*)</image>%;
[download]