One major thing to remember when creating an sort of mystery: as perceptive as your players are, and despite your absolute best descriptions they likely aren't imagining things exactly as you see them. You may have to do a little extra prodding, or hinting, but that's alright. It's probably something their highly skilled characters would have noticed anyways.
Visual aids are paramount. Again they may not be imagining what you are, so maps, sketches, or pictures puts everyone on the same page.
If you'd like to go with the skill challenge route it can limit roll playing a bit and turn it into a series of dice rolls. Nothing is entirely wrong with that, just make sure your players describe what they are doing and why to the rest of the group. Remember that skills and knowledge checks are supposed to represent things that we don't necessarily have the ability to do ourselves. If an impulsive impatient player is playing the pensive thinker allow him to make some knowledge or perception checks to notice things he may have never put together as a player. You want to make sure your skill challenges continue to be fun for everyone one too, so you might consider allowing character's to roll any skill as long as they can find a logical way to justify it RP-wise.
Disclamer: I have never run a skill challenge in saga, only played in them. They can be quite fun when everyone gets into them.