Became a petioner in relation to his power..?
When people die, they should be sent to a plane relating to their worship or alignment, where they become petitioners. Exactly what this means depends on the plane, meaning that in some cases, you end up some nobody in a grueling existence on some blasted plains, forever, whereas if you're a tremendously powerful servant of the high heavens, you become an angel. In the case of evil servants, you can become one of those shitty lower-level worm-daemons, or you're just sent into the meat-grinder that is the blood war. Eventually, whether you're ground down to dust and "die" again or if you're some kind of semi-eternal, you'll become part of the very plane of existence you're on, and eventually be reborn - either as part of that plane, or (partially) into a new being on the prime material (or it's variations).
My point being that whether TNO died or not is irrelevant in this regard; he'd still be supremely powerful. You don't just lose your essence when you die in this cosmology.
The easiest way to think of it is this; the mechanical Experience Points represents the narrative strength of your soul. You accumulate XP because you are accumulating power (part of which is just simple "life experience", you live, you affect your world, etc.) and sometimes this is expended in some ways (this is the basis for the XP cost of magic items in D&D; when you're creating a magic scroll, you're quite literally pouring your soul into it in order for it to become magic). This power isn't lost when you die - you take that shit with you, often to the benefit of whatever plane you go to, since eventually, the entirety of your being (your soul and it's power) becomes part of that plane.
And TNO? He's racked up quite a lot of experience. Not just life experience, either, but literally pumped up his soul by flat-out murdering entire planes of existence worth of people. This also includes all the people that died when he died, because every time that fucker died, someone was murdered in his place. There's an accounting department somewhere in the planes that keeps wondering why petitioners are being sent to the wrong places as if some divine bureaucracy is cooking the books.
Edit:
IIRC all petioners lose the memories of when they were alive too. So goodbye 10000 years of experience (so yes to being depowered).
I didn't see your edit before I posted, and I'm not sure about whether someone loses their memory when they become a petitioner or not (although that would make perfect sense).
However, your memories are not your experience, it's just part of it. In the cosmology, narrative relating to mechanics, it is entirely possible to be an amnesiac with massive XP. TNO didn't
just lose his memory when he died, or - possibly - he simply had no idea of how powerful he truly was, hence limiting his ability. It is likely mostly a minor narrative/mechanical discrepancy, however, which are common in these games.
Edit 2: Also, it
does work
a bit like karma, but remember that just for him to stay alive, for every incarnation, someone had to die due to his actions. There's simply no way even his good-est incarnations could ever make up for that. Not in a million years. TNO was always going to the lower planes, even if we ignore the sin of the original incarnation, whatever it was. His immortality just arguably made things infinitely (in a near-literal sense) worse.