I think we need to remember to decouple the mechanical penalty - that is, how much gameplay you repeat for failing - from the presentation of the failure (death, "And then they all died and nobody heard from them again" Game Over screen, regeneration, etc.).
I've just finished playing the 2008 Prince of Persia, in which Elika catches you whenever you make an error and returns you to the last flat ground you were on. A lot of people said that that took away the threat as well, but it certainly didn't take away the frustration during long wallrunning sequences. On the other hand, games like the Uncharted series have you die when you die, but they're happy to return you to the last puzzle or enemy wave you were on as many times as you like.
I think the physical penalty element is really important. I don't game design has evolved to the point where we can dispense with ideas like a limited number of lives to accomplish a sequence (or all sequences) and absurd penalties for losing them all, and great games get by without them altogether.
The most extreme - and, I believe, the most effective - example of this is Super Meat Boy (SMB). You return to the start of a level when you die with a hideous splatter in SMB, but the levels are rarely more than 15 seconds long, and the period between hitting the obstacle and getting moving on your next attempt is about to second. This leads to a game where players are clearly happy to throw themselves at sawblades and mountains of salt hundreds - thousands - of times just to beat their friends' times. How many games can you think of where you've been that persistent?