Concerning the naviserver: yes, it is a pity, it went this way. I have high respect for the naviserver developers, they had good reasons for doing this. Things look different, if your companies product depend on low-level functionality of the server. Btw, Their latest release is 4.99.1.
concerning ns_cache: if one has to iterate over a couple of hundred entries in tcl, this is certainly slower than doing this in C. For the same reason, many tcl commands (array, info vars/commands...) have a pattern argument. For toy installations, you are right, the difference won't be noticed.
It is no rocket science to program around this problem (used so far only on two places), and it should be possible to use the c-version where available and the tcl version, where not. however, i would think, upgrading the debian distro would be even less work.
I do not believe, that Jon's problem is related with ns_cache.