We've got some very deep levels of dependencies here - up to 10 at most (we're an ISP). I have all the parent/child relationships set up, plus dependencies for everything. (Not monitoring individual switch ports as well yet, though!)
I found that walking the dependency tree took too long, partly because of the depth involved and partly due to the number of checks I was doing. It's now not too bad, where the problem host will get identified fairly quickly.
The problem is, dependent hosts are NOT getting marked Unreachable - they're remaining at the OK state because once their parent is down no further checks are being made. This is the "execution_failure_criteria" that is introduced with Nagios v2 I think.
I don't want to have Nagios waste time checking hosts that should be known to be unreachable, but I would like those hosts to be marked as unreachable on the status map.
I may just have to have a try at modifying the code for this one!