I've read the recent discussion, nobody has mentioned OpenBSD (so far).

We've run into the exact same issues. I believe we have some original
solution, compared to FreeBSD and NetBSD.  Not everything is perfect yet,
but it's getting better.

1/ building correct packages is still an issue. Stuff like libtool does insist
on linking stuff against /usr/pkg/lib first... I've read the buildlink stuff
in NetBSD, there's a lot of useful work (and ideas) there that we haven't
incorporated (probably in another form) yet. The main showstopper is
pkg-config/libtool: both need to be tuned to look for stuff in a specific
playpen, and not in the main system, to be able to build packages that are
not influenced by existing stuff.

2/ shared libraries are a first-class object in the package system. We
fully register dependencies on shared libraries, and we (religiously)
bump library names when incompatibilities occur. For instance, an incompatible
change in libpng would cause a bump from (say) libpng.so.12.0 to libpng.so.13.0.
So, when you update the png package, if some packages still have a dependency
on libpng.so.12.0 (@wantlib lipng.so.12.0 in OpenBSD packing-lists), then you
will keep a stub .libs-libpng package around until all dependencies have been
updated. Of course, all the dependencies need to be updated until you can 
remove this package, but at least that way, you keep a functional system.

3/ once the shared library issue is `solved', you can replace dependencies
before replacing the package that depend on them, provided the dependency
still match (or you could cheat). There's the unpleasant business that some
updates will break stuff, and in a few (rare) cases you have to mark that
the `simple mechanism' will work. (e.g., if package foo-1.0 depends on bar-*,
and you figure out that bar-2.0 breaks that, you have to annotate bar-2.0
somehow to say that nope, you must update foo, even though the dependency
appears to match).

4/ all packages have a signature, that is composed of the pkgname proper
(which gets bumped each time the port gets tweaked in a way that affect
the package), plus the complete list of dependencies: any dependency appears
in the package as a wildcard for matching packages, plus the exact package
name that was used for building. That way, you can determine whether rebuilding
a package is a waste of time (there's the issue of hidden dependencies on the
base system, such as compiler tweaks, that we haven't tried to solve yet).

5/ our ports system systematically builds binary packages anyways, so keepin
an archive of stuff to reinstall is the default behavior.

6/ there's the issue of files that change packages (happened in kdelibs/kdebase,
where some stuff was moved from kdelibs to kdebase recently), which means you
have more or less to update `both' at the same time.  Our pkg_add should be able
to cope with that soon...

Just to give you some possible elements to solve this hard problem...