Allow downstairs to be marked as “secret” so that they don’t show up unless searched for or by stumbling onto them (in which case you fall down them). Use this specifically for early hidden branches, like Goblin Town in EvilHack.

Award some experience points when the hero discovers a trap door in a “Vlad was here” closet by searching for it (not by triggering it), because this demonstrates that they are learning that such closets contain trap doors.