Indeed, I never mentioned this point but speed comes first.
I'm willing to use enormous amounts of memory, right now, because it does respond quickly enough (Generating some 200 sentences in 1 and 1/2 seconds), but if it was any slower than that people using it would probably get frustrated with it.
This, of course, limits largely what can be done - but I'm still curious if there are solutions to be found.

JP,
-- Alexander Widdlemouse undid his bellybutton and his bum dropped off --

You might want to read perlguts, then. :) If speed comes first, be prepared to burn lots of memory. Speed does not rule out a DB-backed solution, however, as they all do caching and will be rather fast (though probably not as fast as all-memory hashes) once the caches are populated.

Consider using Devel::Size as you try different things to get an accurate (as long as you don't have coderefs in your hashes) reading of memory used by the different structures.