Despite being mainly a 3.5e (and now Pathfinder) guy, skill challenges are a concept that really interested me about 4e. Since the first time I opened the 4e DMG I wanted to use them in my games, but even in the few 4e games I DMed, there were times when skill challenges were just a bit... awkward. A predetermined length made the lengths of certain challenges seem arbitrary, and an undesirable amount of meta-game exposition was needed to get the challenges rolling.
Perhaps this would have smoothed out over time as I became more deft in my use of this tool, or as my players grew more accustomed to jumping into it, but as there are still many articles offering advice on the subject, I suspect it takes a truly skilled hand to make skill challenges a seamless part of a game.
A week or so ago I had the good fortune to run across a link to this article by Ari Marmell regarding the same subject. His answer to the problem, placing the decision of which skills were most important to the challenge almost solely in the hands of the players, struck me as a step in the right direction, but not quite at the logical conclusion yet.
Choosing which skills to use and how to use them is great, but what about announcing the challenge started in the first place? Why not leave that to the players as well?
Player-Announced Skill Challenges
In this model for skill challenges, the DM is only responsible for setting the skill check DCs (not hard to do on the fly with the easy/moderate/hard paradigm) and deciding how long the challenge takes to complete. However, if the challenge comes to a nice close before this predetermined length is reached (such as may happen in a roleplay-heavy skill challenge), just let it end and give out XP for the complexity you had decided upon; think of it in the same terms as if the PCs had cleverly used powers and tactics to defeat an enemy using less time and resources than you anticipated they would.
The challenge may still be failed as normal, but I'd recommend, if there's no clear in-game reason for it to be 'over' after the third failure, you let the PCs keep going at it and just don't award XP.
Skill Challenges in 3.X/Pathfinder
As for XP, hand out experience points appropriate for a CR equal to the average party level – 4 per level of complexity of the challenge (use the same rules to determine complexity as detailed in the 4th edition DMG). So, a group of four 5th-level PCs that has just overcome a complexity 2 skill challenge would get 150 XP each.