Sorry, I don't have any pointers on bidirectional lookups, but have you considered using DB_File to tie your hash to a database file?.
It looks like your data will map nicely to a BTREE and lookups should be fast. You could run the database completely in memory or tweak the cache size to suit your requirements. It will be easy to try with your existing code if you want to give it a whirl.
I tried a single hash btree from your example above ( 'aaaa' - 'zzzz') and it created a ~11Mb file, so it seems to pack pretty well.
