I just had this (perhaps not completely novel) idea: the deeper the dungeon level, the less it conforms to the natural world known by the characters.
The first three dungeons levels might be quite naturalistic—vermin and low HD humanoids living sensibly (if violently) within the circle of life and whatnot. In one or two places, weirdness might peek through from the depths in the form of, for example, a magic well. Four to six levels down, weird elements become more common, and the relationships and behaviors of the inhabitants become less understandable. The dungeon, below level six, breaks down in terms of cause and effect. Fairy tale logic dominates the lives of inhabitants, and the structure itself sprawls in non-euclidean ways.
This could also differentiate one dungeon from another. Most dungeons, in the first few levels, would more or less resemble each other. The true and unique nature of a particular dungeon's weirdness would only be revealed within its depths.