According to the NWN manual, the Ranger Trackless Step is as follows:
The ranger gains a +4 competence bonus to Hide and Move Silently checks when in outdoor areas.
So I'm going to go out on a limb here and say that caves are not outdoor, no matter how much sense that may make to your dark elf ranger. I'm also assuming, based on observation, that the outdoor area must also be natural.
So the criteria are exterior, natural, above ground.
By the way, Ajari Outskirts are fixed for this in the next update, coming REALLY soon.