I'm glad I looked into this again. It appears to be a bug (well, it is at least an "interesting" algorithm). Here is my test code:

#!/usr/bin/perl -w
use strict;
my $key='a';
my %check=($key=>1); # Used to find keys that hash similarly
my %fill= %check;    # Used to show hash isn't expanded
my %grow= %check;    # Used to show when hash does expand
$|++;
while( 1 ) {
    $grow{$a}= $check{++$a}= 1;
    if(  1 == substr(%check,0,1)  ) {
        $fill{$a}= 1;
        print %grow." ".%check." ".%fill." ".keys(%fill).$/;
    } else {
        delete $grow{$a};
    }
    delete $check{$a};
}
[download]

1/8 1/8 1/8 2
1/8 1/8 1/8 3
1/8 1/8 1/8 4
1/8 1/8 1/8 5
1/8 1/8 1/8 6
1/8 1/8 1/8 7
2/16 1/8 1/8 8
2/16 1/8 1/8 9
2/16 1/8 1/8 10
2/16 1/8 1/8 11
2/16 1/8 1/8 12
2/16 1/8 1/8 13
2/16 1/8 1/8 14
2/16 1/8 1/8 15
4/32 1/8 1/8 16
[download]

I'll have to find some time to look at the source code...

Update: I submitted a patch to fix this but it was mostly not understood and so I'm pretty sure it didn't get included. *sigh*

Update: Many months later I tried again and managed to get the patch accepted that time.