Assuming you're running NetBSD 1.4, try installing patch-01 from
ftp://ftp.netbsd.org/pub/NetBSD/NetBSD-1.4/patches/patch-01-in_var.gz

Your problem sounds exactly like the description of the problem that
patch-01 fixes.

> The basic issue is that some web hosts (search.nytimes.com is a good
> example) are not reachable from my internal (ipnat) hosts.

--Brian;