Basically, there is no generic way to have guaranteed backward compatible generic (de)serialisation

Well, actually there are at least two ways: First, don't change the serialization format between minor versions. Second, keep the old code around -- it sure *used* to parse that old format. Storable is fast and compact, but I've almost sworn off using it because of this. Data::Dumper plus gzip should be good enough.