I don't think permadeath is appropriate for every game. To me, it depends on the variety provided in each playthrough. If starting over means that you are faced with no new choices, no new powers, no new monsters, no new levels, etc, then permadeath probably isn't a good choice for that game. Redoing everything that you've already done simply isn't fun.
That's why randomness is such a key part of roguelikes. While the player may be a bit frustrated at dying, there should also be excitement to see what the next run will have in store. And while randomness necessitates some degree of luck, luck can also contribute to this feeling, this idea that anything can happen, that the same game can surprise you each time you play.
While some may enjoy permadeath for just the added thrill factor from the risk it provides, I don't personally feel that is enough. I've never understood permadeath in MMO's, where you must spend hours grinding to get back to where you were, nor even in games like Diablo, which has random dungeons, but static gameplay and choices.
So it is usually my goal to make repeated playthroughs as interesting as possible. For me, that's the draw of a roguelike, this sort of unspoken promise that each time I play will be a brand new experience.