Very interesting. I'm curious, have you considered nixos?
With Nix, we can have version guarantees in all of our Docker images--including the cached images.
http://gregoryszorc.com/blog/2014/10/13/deterministic-and-mi...
`RUN apt-get install some_package=<version>` If you want a newer version, update the Dockerfile with the version you want.
I understand all their philosophy, but they should allow for flexible runtime dependencies without the need for rebuilding packages. Perhaps with a second hash or something, to sign dependencies.