I've verified this issue with both

    perl 5.6.0 / Storable 1.013
    perl 5.6.2 / Storable 2.13

I looked at the  Storable.xs code in 2.13 and turned on the 
DEBUGME flag and reran my test retrieve code. (test.pl)

    #!/usr/bin/perl
    use Storable qw(retrieve);
    $Storable::DEBUGME = 1;
    retrieve(shift);

Then ran it

    ./test.pl out-of-memory.storable

and got this output (truncated to show the error)

    ** extending kbuf to -184127888 bytes (had 128)
    Out of memory!

I tracked it down to retreive_hash() and this code

    KBUFCHK((STRLEN)size);  /* Grow hash key read pool if needed */

Storables are created every couple of days that trigger this
bug and because these are profiles and we have no way of 
trapping the exception, our we have users that are kill 
httpd processes each time they attempt to load our site 
until we remove the offending storable file.

I've attached the 'out-of-memory.storable' file so you can
easily reproduce this problem.  From my basic knowledge 
I'm wondering if we could just ASSERT if you attempt to grow 
the hash key read pool if its not a positive integer.  (I 
stress basic) :)