It occurred to me that Geert Hendrickx wrote in gmane.os.netbsd.devel.packages:
> That's easy to solve.  The essential thing is the ordering, and apparantly
> it's not ok yet.  

I don't claim to be a python expert, but judging by looking at the code, it 
seems that the dependency chain is built "bottom-up" using the +REQUIRED_BY
files in /var/db, and not using the contents of the pkgsrc dir. There appears
to be some code to inspect the pkgsrc dir, but it isn't called, probably 
because of speed considerations. Reading a file from /var/db is much faster
than calling 'make show-var VARNAME=DEPENDS', especially since every package
is inspected several times since there doesn't appear to be any caching of 
this data. There are several reasons why this isn't the most ideal 
solution:

1) It assumes that /var/db/pkg/*/+REQUIRED_BY is valid, but unfortunately
   this is cannot be guaranteed, especially when 'make replace' has ever
   been used, as it effectively zaps the +REQUIRED_BY files. You probably
   replaced pcre yourself at some point, and didn't update kdelibs afterwards.

   You could get around this by inspecting +CONTENTS as well, since this 
   provides the required dependencies for a given package, but it's 
   probably harder to parse.

2) It ignores newly introduced dependencies, since the dependency chain is
   built based on the dependencies of the previous, outdated, package. If
   a new version of a package needs additional dependencies, these will
   be ignored.

3) Similiarly, changes to /etc/mk.conf are ignored.