I think the trick is to only ever append at the end of the string, and to destroy the string when you found something:

my $str = '';
my $tmp;
while (read($handle, $tmp, 32*1024)) {
    $str .= $tmp;
    while ($str =~ m/($re)/g) {
       # have we read up to the end?
       if (pos($str) == length($str) - 1) {
            # yes - discard our attempt
            last;
       }
       my $data = $1;   
       # do something with $data here

       # and now destruct our pour string:
       $str = substr($str, pos($str));

       # and start from the beginning again
       pos($str) = 0;

    }
}
[download]

This code is untested, but it should give you an idea of how to do it.