I'm a bit late in this thread, but I have a similar problem: evaluate the size of a big hash that I have in memory.
I searched perlmonks for some clue on this issue, and I found this thread. I've read your ideas, and I found them very interesting. Anyway I came up with a different approach, and I'd like to share my idea with you so that you can give me feedback.
The idea is quite simple: I build the hash and then use Storable::freeze (see module Storable) to freeze it in memory, and then evaluate the length of it. I had this idea reading the man page of Storable module: here is an example from the man page:

use Storable qw(store retrieve freeze thaw dclone);

%color = ('Blue' => 0.1, 'Red' => 0.8, 'Black' => 0, 'White' => 1);

$str = freeze(\%color);
printf "Serialization of %%color is %d bytes long.\n", length($str);
[download]

What do you think of this approach?

marcos