All the "practical" package managers rely on relatively terrifying hacks and heuristics to get around this. I have been looking through Debian metadata, and I am very surprised at how unsound it is. The metadata is very tightly coupled to apt-get ("virtual" package handling, etc.) Not to mention that all the algorithms basically only work in one direction (going forward, not backward).
It appears that some academic/niche package managers are incorporating SAT solvers.
"Managing the complexity of large free and open source package-based software distributions"
http://scholar.google.com/scholar?cluster=162491025473640248...
More references:
http://www.mancoosi.org/edos/references/
Anyway the root problem is that C headers and other language-specific interfaces are not always a good way to interface software components... developing more stable binary protocols would greatly ameliorate the versioning problem.