Maybe I should back up a little. I had an idea for a story that revolved around a modern fantasy setting where magic was common place and so was the variety of races. Their technology was lacking in some areas and superior in other areas as their magical prowess made necessary. The problem was, this was going to be a detective story. So, how do you track down killers and solve crimes in a fantasy setting where magic is common, people can turn invisible, alter memories and do innumerable horrible things? I didn't know until that first skill challenge. After that first skill challenge it was clear, scrap the story idea and run this as the central idea behind a campaign.
Without getting too much into it right now, I decided to revive the planescape setting, converting a lot of non-existent stuff to 4e and then reworking or adding a lot of the current planar setting to make the game make sense in the 4e cosmos. The players were to be the Custodians, a group of people taken from each of the factions and put together under the command of the city in order to investigate and solve crimes that demand special attention. One of the twists was that everyone picked their own faction. Players got missions for each major arc that they tried to successfully complete. At the end of the major arcs, players got a chance to guess one other player's mission.
This seems like it would create conflict, and perhaps it would have, if not for additional rules. First, the Custodians are supposed to be outside of the faction wars. So, if the Custodians are caught, player discovered in this case, performing a task for their faction, the faction isn't allowed to act on the mission results. To do so would be to invite punishment by the Lady of Pain. Successfully completing missions would never effect players either, as Custodians are protected by the Lady of Pain. To harm them would be to invite wrath upon your faction. Obviously, factionless groups, monsters, etc. have no issues hindering the players physically, and factions and mess with their minds just find. What does this mean for the players practically? Well, completing a mission grants bonus xp to the whole party. Discovering a mission grants bonus xp to the whole party. This creates an environment that is supposed to foster fun competition without it getting down and dirty like say, Paranoia.
So far it's been pretty good. People tend to forget their tasks, even with me giving them copies of their mission every session. No one has gotten upset or frustrated though, so it's not a total failure!
Back on topic here, I decided to set up an investigative system built around the skill challenges. I believe that skill challenges should be somewhat open ended and as long as you can describe what you are trying to do given the use of an appropriate skill, it should be allowed. This means a lot of work on my end. I spend a lot of time before each session coming up with ways that players might use skills, or at least how THOSE skills might be related to OTHER skills. If the skills are related I just up the DC on one of the skills and would give out the same information they would have got given a different skill use.
Skill challenges can ruin the flow of the game at times, especially if you have to state each time you are in a skill challenge and then dole out which skills are appropriate to use. What I do is use two differently colored poker chips. After describing the scene for the players, the first player to act becomes the first of each round. Once the player has acted there are three possible outcomes.
1) A yellow chip is added to the table, indicating success and that they are in a skill challenge.
2) A blue chip is added to the table, indicating failure and that they are in a skill challenge.
3) The player decided to aid a friend, in which case 1 and 2 are just delayed.
The biggest problem is creating the right conditions for failure and making sure that failure means something. I've opted for a pretty basic rules set for failure, following the idea that all information is valuable and there need to be many ways to get it. An investigation game is only as good as the information presented and getting stumped because they failed one challenged and missed crucial information just plain isn't fun. This means that there has to be penalties without stopping the actual game story. This list is what I have used so far.
1) Each scene has two failure limits. The first failure limit indicates that the difficulty of the encounter has decreased, lowering the party's overall XP reward. The second indicates that the scene ends and the group has to move on elsewhere for information.
2) The party receives incomplete information as the scene ends. This has almost always lead to a fight scene as the party was lead into the mastermind's devious trap. Usually the fight reward is the rest of the information or at least additional information that might lead to another skill challenge.
3) Punishment as it is recommended in the DMG. This actually isn't bad. Players lose healing surges, they become distracted lowering their initiative for the next fight, etc. These are all acceptable actions that show the consequences of failure without really stopping the investigation.
4) Missed information results in a harder encounter down the line as a result of the missed information, prior to the climax of the arc. This is always coupled with enough information during the encounter itself to reveal what was missed and how that might have been avoided.
5) Tangible rewards. A lot of scenes have specific items and treasure hidden about as rewards for doing well enough to spend actions just searching the premise. In this case, the punishment is not getting that stash of gold or potions, or even magic ritual or item. This is an easy one to use, and the players might never have a clue.
The key is that information is never the reward of the scene, just the speed at which it is gathered. This might mean adding extra encounters as the game story progresses, but that's just part of the fun an excitement running this type of game.
Give an investigation encounter a shot in a game. Who knows? The players might love it, and so might you, the person running the game.