The next obvious solution is to make separate packages for every version of library that the software uses. The problem is that there is no real convergence on “commonly-used” versions of libraries. There is no ABI protection, nor general guidelines on versioning. You end up having to package each and every minor version of a library that the software happens to want.
I don't understand why this is a problem exactly. If a dev runs and tests against a particular version of a library, use that version. Even minor updates in libraries can cause problems. If the library has a security issue, blacklist the version and force the upstream dev of both the library and the app to acknowledge the issue and release a new versions of their projects.