What purpose does Storable serve if one can't rely on it to recover the data again?

Wow, you were using a really old version of Storable, and you upgraded to a not-quite-so-old version! The current version, 2.15, has various switches you can twiddle to configure just how much backward and forward compatibility you want.

The situation you encountered was a frequent complaint from users, but no-one stepped up for a long time to fix the problem. Code speaks louder than words. I think it was only in the run up to 5.10 that the issue was dealt with.

The best Perl solution is to use Data::Serializer, which will allow you to switch the underlying serialisation mechanism used with minimum changes to the client code. And better contenders to the serialisation crown would have to include JSON and YAML, since implementations for both exist in other programming languages.