I think you are misunderstanding where people come from with this: it's not the randomness; it's games where when you lose, you start over from the beginning - not the last save/checkpoint/whatever. What this indicates is that, in the broader gaming scene, this is the defining characteristic of Rogue(likes), not the permadeath.
And in that sense, something like Hades or Everspace or FTL or whatever absolutely fits the bill, even if on your next run - from the beginning - even if you are very slightly stronger the second [third, fourth, hundredth] time around.
I understand that there are still some purists out there who work themselves into a tizzy over splitting these hairs. But it's okay for there to be subgenres. It's okay for colloquial terms like this to have fuzziness to them.