Perception might be an odd but viable alternative. Her understanding of how to search allows insight into hiding, so Per + Stealth. Mostly I'd use Dex + Stealth though.
In Sub Rosa there was a scenario featuring a faerie market, and there was a contest of foolishness - in order to win, you rolled Enigmatic Wisdom MINUS Intelligence in order to try and win.
Cathelineau: never would I substract prs from a stealth roll. A positive characteristics has to have a postiive effect. In fact, someone with 5 presence is more able to hide because in the contrary of the one of -5, he is more conscious of his presence.
In the case of darkwing example, I'd say the fact that intelligence is substracted is illogical but I understand his point. In my opinion, I would have put an intelligence + enigmatic wisdom roll, but the ease factor would have been higher for those with high intelligence (thus negating their intelligence).