Tie::Hash::TwoWay does actually store the mapping in two different hashes internally, it just doesnt have any way to specify which direction to operate on, it tries the "primary" direction, and if the key doesnt exist, the operation is tried on the "secondary" direction.

In any case, at lunch today, i designed a tie that does what i need, i'm about to implement it. I'll post about it, and submit it to CPAN, hopefully by the end of the day!