I tried this recently - I had my PCs infiltrating an enemy city, but there were places they could have rested. Trick was, there was another group also infiltrating the city, that was after the same plot item as the PCs.
Basically, I had a skill check where the failures made the last encounter harder. Rests counted as failures on the skill check. Fail the skill check, and the other group got there first - fail it badly enough and the other group gets away with the item before the PCs get there, and instead the PCs have to run from the city denizens converging on the location. Basically, the failures meant lost time, which not only put the opposing group in a better position to get the item, but also gave the defenders more time to figure out what was happening and get their act together (adding to the budget and difficulty of the final encounter). That said, it was the first time I had used coup-de-gras, more through a lack of opportunity (with so much healing, the PCs are rarely down for long) and those MV brutes pack a huge punch, so I can understand the player being unpleasantly surprised.
I told my PCs up front that resting would count as failures on the skill challenge, but not the exact mechanics of what failures in the skill challenge meant.
The encounters were an n+1, then 3x ns then an n+2 to finish. The party ended up resting twice (basically once after every 2 encounters), which were its only failures in the challenge.
I think my PCs are pretty conservative with their daily powers, which hurt their endurance and required that they rest more often (there were definitely PCs with unused dailies at the end). Additionally, while they have a lot of healing (with a pacifist cleric, a tactical warlord and a paladin), they don't really do much damage (the others PCs being a wizard and a 2 weapon ranger who was only there for the last 2 encounters). And, even with their rests, I killed one PC through a combination of him being stupid and unlucky - he deliberately provoked an OA from a demonic minotaur brute (in order to damage it with his flame shield), got taken down, then the raging minotaur coup-de-grased him on its turn, killing the PC (and the minotaur - the flame shield took off his last HPs). However, given that this was the first time I've used CDG, and given that the PCs aren't yet used to the damage MV brutes can pump out, I can understand how the PC in question really didn't expect that to happen.
It went fairly well, though I've still got a lot of areas to improve (giving my PCs descriptive info to work with is a big one). That said, I like the ideas in this thread and probably will try them in the future.