in our database, we have some frozen Perl hashes that were created with […] Storable
That right there is your problem. Storable makes no promises about binary compatibility across different releases or different perls. You do not want to use it as a serialisation mechanism. It is not a good idea for anything except intra- or interprocess communication between forks of the same process.
Most likely you want JSON. That will also decouple your data from perl. JSON::XS even happens to be faster than Storable, and by no small margin (which is where the simplicity of the JSON data model pays off).
Makeshifts last the longest.
