Or maybe you don't let some convoluted system ruin your game, when they fail the "challenge".
Upon suspecting the Duke to be a demon, if there were clues being led to it, the party has already passed the challenge. Why then force them to backtrack to failure? Why not let them just go around asking and let them find the info needed to "prove it".
If you don't want to RP it, then ak the DM for a summary of things found over searching, people met etc. You get the same result of the skill challenge which is contacts and info, without the needless chance of failure.
Possibly your example is just a VERY bad one, as it would leave failure as a chance that could completely screw the game up because of the mechanics.
-gather information (Endurance, Diplomacy, Streetwise)
failure here means the game is over
-find a way to break the curse (Arcana, History, Religion)
failure here means the game is over
-get to the Duke without being noticed (Athletics, Acrobatics, Stealth)
failure here means combat at least
The first two cannot end in failure, thus the problem with designing a skill challenge as such because your challenge could stop the game, when you have living healthy characters to continue it.
So they fail to gather information due to the skill challenge, and jsut decide to leave the town cause the Duke must be an upstanding guy and there is nothing left to do here.
That Is where using it as a resolution works better, when needed. Still the last one I wouldn't use a skill challenge, it is likely just going to be a pass fail. Get noticed once and the alarms have gone off and no more sneaking its battle to battle until you achieve your objective.
Best leave me with the previous information before you turn my opinion on skill challenges fully negative again, such as your example is startign to do.
The game won't end if the PCs don't find evidence during the challenge -- the demon possession will simply continue and depending on purpose will commit an atrocity or two before the behaviour will lead to eventual discovery.
The game's direction will change based upon success or failure, but the world and the characters within will continue regardless.
Now if the DM has absolutely nothing else prepared for the session and was depending on PC success to lead to the adventure then yes, he screwed himself over nicely.