As mentioned in the parent, I found a bug in the caching code. I'm not worried about the degenerate case, though obviously my approach incurs a penalty in worst case scenario. I was going to benchmark your code, but couldn't get it to pass my updated validation routine:

sub verify {
    for my $letters (1, 4, 26) {
        my $input = join '', map { ('a'..'z')[rand($letters)] } 0..200
+00-1;
        my @RobertCraven = RobertCraven($input);
        my @hdb = hdb($input);
        my @kennethk = kennethk($input);
        my @xxx = xxx($input);
        die "Mismatch 1 ($letters)" if @RobertCraven != @hdb;
        die "Mismatch 2 ($letters)" if @RobertCraven != @kennethk;
        die "Mismatch 3 ($letters)" if @RobertCraven != @xxx;
        for my $i (0 .. $#RobertCraven) {
            die "Char mismatch 1($letters, $i)" if $RobertCraven[$i] n
+e $hdb[$i];
            die "Char mismatch 2($letters, $i)" if $RobertCraven[$i] n
+e $kennethk[$i];
            die "Char mismatch 3($letters, $i)" if $RobertCraven[$i] n
+e $xxx[$i];
        }
    }
}
[download]

Does it pass on your machine?

Update: Parental code now passes tests.