I think you're right, maybe I underestimated the challenge presented by the games because it turned into an unfortunate meme. I think simply calling them "hard" doesn't do them justice. They excel at putting you on edge, every Souls game is a bit exhaustive. They present a system where death really means something bad for the player (instead of AAA games where you can kill yourself real quick to reset the stealth bits instead of going for a shootout, fuck Uncharted 4) and yet it's ever present because of the mix of hard hitting enemies and ridiculous death traps. I think it's more comparatively punishing than hard. You can't afford to make mistakes and you know you will make them, which makes the experience feel more daunting. Which personally I think it's fucking awesome.
I think perseverance (or endurance?) are a
facet of being hard. To me, that sounds like what you are describing. An example would be the shmup genre. Beating a shmup on one credit has more to do with practice and endurance than fast reflexes. Your blood gets pumping as the final boss approaches, you lose your cool, and then you're dead after 20 straight minutes of expert dodging. As you put it, "[Souls games] excel at putting you on edge" and this is exactly right. It's not like each individual enemy is impossibly hard. It's not like each corridor or stairwell or catwalk is booby-trapped. However, put these together and it's a challenge merely to persevere.
That's a good insight on stealthy mechanics and amping up the consequences of death. I don't think strict consequences
necessarily equate to hard (that isn't what you said, of course), but it does require more endurance out of the player. Just a different facet of "hard", I suppose.
My problem is that this unease at the prospect of failure in a game shouldn't be an unique trait. The lack of tension in most modern games eventually makes them feel a bit boring outside of obvious spectacle or nice stories and shit.
We used to have a market that was uniquely designed to give us hard-but-fair experiences and it worked shockingly well: arcade games. They were sold to two customers, the player and the arcade proprietor. If it was too hard, the players wouldn't play and the arcade proprietor would lose money. If it was too easy, the player could spend minimal money to play for a long time and the proprietor would also lose money. I have no clue how this would be imitated in today's market other than perhaps looking back and studying the elements that defined hard-but-fair games from the past.
Now, please don't misunderstand. While I love arcade design, it's not for everyone and there are reasons why it faded away. But it's worth remembering from where "hard games" arrived.
The last level on The Last of Us hits it home nicely as well because the game puts you in this really urgent mindset. You gotta go fast, take fools out, stakes are high and you feel the rush in the gunfight. The game achieves this tension through a completely different method than Souls game and it's pretty much as effective at getting you invested and keeping you focuses. If you have no reason to pay close attention to what you're doing, eventually you zone out and since games are long experiences you won't remember most of them. But you do remember Sen's Fortress. And you do remember Valley of Drakes, Demon Ruins and so on.
"Memorization" gets a bad rep, but there are few mechanics in gaming more satisfying than figuring out a pattern or a run, executing it well, and emerging victorious. We remember these sections because we
had to remember these sections. We couldn't have proceeded through them otherwise, and I think that's something to be celebrated and studied and tweaked, not avoided.
Good point about being "invested" in the game for the purpose of focus. Focus, intensity, whatever you want to call it is what makes games thrilling. Many ways to achieve that feeling, but difficulty is probably the most reliable (at the risk of alienating unskilled players). Narrative tries to achieve focus through different means (at the risk of alienating people who want a challenge and/or prefer to engage with the mechanics instead of the plot).