You could make the number of accesses between cleanings proportional to the size of the hash. That maintains O(1) average overhead for keeping things clean, divided unfairly. Perl internally uses many variations on this strategy.

There are scenarios in which this compromise is the wrong thing to do. My answer to that is that no solution ever strikes a perfect balance. Find a good enough one and move on. Make it pluggable (as you suggest) if that isn't good enough.