My favorite immortal supervillain story is the one of Vandal Savage from the DC Animated Universe. The first time he shows up, he learns in his immortal life that the most unstable moment in global history was World War II, and travels back in time with only a laptop with advanced technology schematics and supplants Hitler as the head of the German Regime and actually wins World War II. Members of the Justice League then travel back in time and fight in WWII to stop him.
There's a second story with him that isn't that notable,
save for one awesome moment with Batman.
Then the third story is one of the best episodes in the series where it appears that Superman dies, but is actually flung 30,000 years into the future, where Vandal Savage was the only living human after he had accidentally wiped out almost all life on the planet with some gravitational doomsday weapon. The isolation and reflection that it caused meant he turned into a humbler and warmer person with extreme regret for his past self and his atrocities. He started building a time machine, but he couldn't go back in time to any point when he was alive (wait, then how'd he go back to WWII?), but since Superman shows up and was taken out of time, then Superman could go back with specific instructions on how to stop past Savage, and when they use the time machine and Superman goes back, the future Savage fades away, thanking Superman for allowing him to rectify his heinous crime.
