I was considering some sort of size limited tied hash

Since some of the earlier posts seem to be concerned about the performance of a tied solution, you might consider a straightforward subroutine instead. You could use a closure to store both the cache, and an array holding the insertion order (for use in deleting the oldest value). Here's a quick example I worked up. This is not extremely well-tested, but does appear to work. YMMV:

# simple test
for (0, 1, 2, 3, 4, 5, 6, 0, 0, 4) {
    print "$_ ", cache($_), "\n";
}

{
    my @order;
    my %cache;

    sub cache {
        my ($key) = @_;

        # this number would need tweaking
        if (@order > 5) {
            delete $cache{ shift @order };
        }

        unless (exists $cache{$key}) {
            push @order, $key;
            $cache{$key} = some_expensive_func($key);
        }

        return $cache{$key};
    }
}

# here is where you would build your statement handles
sub some_expensive_func {
    $_[0] + 5 * 3;
}
[download]