No, I can't go for that. I find it utterly absurd artificially to reduce every possible approach to a problem to approximately the same arbitrary chance of success, and to treat a "failure" on a dice-roll as boding failure for the whole enterprise regardless of context.
Often enough, the best solutions call for NO rolls at all.
But you already do that with combat... and the skill checks that you already use.
Besides, who said anything about being arbitrary? Absolutely, you should be using appropriate DCs for skill challenges... just as you would for any skill check.
Okay, let me try this another way...
I've discovered three things that, for me at least, make all the difference in running a skill challenge.
#1. Don't let the players know that they are in the middle of a skill challenge. Once you do that, the roleplaying goes out the window. Like you already suggest, for each stage let the players figure out what they want to do, let them role play it out a bit, figure out an appropriate check to roll based on that role playing, determine consequences for success or failure, roleplay out the results and then move on to the next stage, letting the players choose the next stage of the challenge, if possible.
#2. Be flexible and creative with the successes and failures of the individual skill checks. The skill checks don't have to mean just +1 success or +1 failure. Perhaps a certain check can grant a bonus to later checks in the challenge. Perhaps failing a certain check could inflict a condition or cause the character to lose a healing surge. Maybe a success or failure illicits a particular response from the opposition. Or maybe it triggers an unexpected combat encounter. There's a lot of options.
#3. Don't hinge the success of the adventure on the skill challenge. The way I see it, if the players are looking in the right direction, they should eventually find what they are looking for, regardless of the skill checks. Instead use the skill checks and challenges as a way to spice up non-combat action in the same way you might use a random encounter. Total success or failure at a skill challenge should provide either an extra useful benefit or an unexpected complication.
To use a vague example...
The PCs are a trying to track down a BBEG who's laying low in a large city. With each successful skill check, they not only earn a success, but hear a randomly chosen rumor about the BBEG from a pre-generated list. Success at the challenge means the PCs learn the location of BBEG's hide-out without drawing attention to themselves, and have the advantage of surprise. Failure means they learn of the BBEG's hide-out, but words gets the BBEG about their search and he's ready for them.