I've added a tsort phase to the output of 'pkg_chk -l' - is
  that pretty much what you had envisioned at that point?

I had already made a hand-written pkgchk.conf that went from less to
more complicated, so just prepending dependencies was enough for me.
But tsort is even better (and -g should get this too).  Probably
obvious to you, but this avoids recursive use of pkg_add, and
therefore needs a lot less PKG_TMPDIR space since only one package
need be unpacked at a time.

  I tend to use pkg_chk with -B, so an updated dependency would
  be cause for a package to also be updated even if its version
  was unchanged, but pkg_add -u would not update in this case.

The man page says "check" about -B, but I think this means "treat as
mismatch if 'pkg_info -b' output differs".

  Hmm - if you did not mind the order in which it ran you could
  just run 'pkg_chk -l | xargs pkg_add -u' and rely on pkg_add
  to skip those that did not need updating. In fact, with your
  change to prepend dependencies to the list that should just
  about cover the order (though ideally a tsort would get it
  completely right)

Would need -f, or perhaps pkg_add needs -b to cause -u to treat
differing build info as differing.  Perhaps this should be the
default, although I think PKGREVISION bumps are supposed to address
this.  But someone might update tiff, notice a shlib bump, and update
emacs without cvs update, getting a binary package that has the same
version but really does need to be updated.

  I use the output of 'pkg_chk -l' directly as a list of files to
  copy to a remote machine, so the pkg_dir in there would clutter
  it for me. Would you be happy with an option to display the
  pkgdir instead of the pkgname, or would you want both?

Sorry, I meant -i, when generating a list of packages that need
updating, so I get this:

devel/popt popt-1.7nb4: version mismatch - popt-1.7nb5

(which wasn't particularly machine-parsable to start with), and gives
me (and scripts) the directory to cd to for 'make replace'.  I don't
want to let pkg_chk kick off make replaces, since I want to bound
lossage, and for cases like this (absent audit-packages complaining) I
don't feel the urge to upgrade.  It would also be nice to tsort these.