Sounds at least a little similar to your old character in
Paths of Legend: The Azgundi Tournaments.
The Shadow Knight, AKA The Lord of Shadow, is a God of Redemption. In mortal life, he was Lord Aluan Velestri of Azgund, the last of a noble Azgundi family who secretly (at the time, it is relatively common knowledge now, at least among the faithful of the Lord and Lady of Shadow and their associates) trained as assassins, carrying on a family legacy of killing people in places of power whose ambitions had strayed too far into the otherworldly and tyrannical. Velestri died at the hands of the Serpent, an immortal force of evil, during the Shadow War and was resurrected. The experience changed him and he became a paladin, offering redemption to those on the evil path, though still retaining his skills as an assassin should they refuse. It is said that The Shadow Knight and his wife, the Silver Shadow, used a magical flying vessel called The Phoenix during the last battles of the Shadow War and use the ship even now, to explore the vast expanse of the planes beyond the mortal realm.
Actual phoenixes are quite rare, existing mostly in legend and fable. The Phoenix is a powerful symbol of, ironically, evil among certain elf clans. Elves hold all life sacred but believe that elven souls return to the source of life upon death, to be reborn. The phoenix, in some elven fables, steals elven souls upon death, taking them for its own selfish desires, causing them to reborn in non-elven bodies. Among the Drukkar, the phoenix is a creature of omen and prophecy, along with a variety of other creatures. A child born under the sign of the phoenix ascending (the Drukkar have a complex system of astrology based on constellations, sun and moon positions, and other phenomena) will bring prosperity to the tribe after a long winter. A child born under the sign of the phoenix descending signifies a time of suffering and death for their tribe but will then rebuild the tribe to be greater than it was before.