But I have no control over what version of the tool my application will encounter in the wild.
To a certain degree, this will be a problem with any module you use. Versions change, internals change, and incompatibilities creep in even when they aren't intended. The only way to be sure your application will work is to bundle specific versions of the modules it needs. This isn't so much a perl thing as a general issue with componentized software.
In the case of core modules, you at least have a simpler target. You can test against the specific perl versions you want to support. But even so, distributions will modify them, people will install newer versions for features they need, etc.
By the way, Storable rocks. It's massively faster than Data::Dumper, highly cross-platform when you store in network order, and as mentioned elsewhere the newer versions try hard to work across version and format changes. It was a great day for perl when we got a fast serialization mechanism in the core and I'd be very sorry to see it go.