Earlier quoted context omitted.
Exherbo and Gentoo both solve this problem with something called "slots". Namely, you can install various slots of a package, you can depend on a slot, etc. In Exherbo you can tell optionally one package to runtime-depend on the slot of another package that you built it with.
I love slots. The Gentoo eselect system is way ahead of etc-alternatives or some of the other package select tools I've seen. Slotted binaries are easier though; slotted libraries can get complicated and get into some crazy dependency hell.
ABI breakages are far less painful than on gentoo.