Hmm. Let's see if this concept will work...
Step One, begin with a Pleasure Devil, from Fiendish Codex II. CR 11, 12 HD, basically a more powerful, seduction-oriented Erinyes.
Step Two, take all six levels of the Fiend of Possession prestige class from the Fiend Folio. CR 17, 18 HD.
Step Three, find some way to increase the caster level on its innate spell-like abilities by 4. (Homebrewed variant of Practiced Spellcaster?)
Step Four, using the rules on p. 156 of Libris Mortis, apply the Lich template, creating a Lichfiend. CR 19, 18 HD.
Step Five, if allowed, use the rules on p. 156 of Libris Mortis as a guide to apply the Demilich template, creating a Demilichfiend. CR 25, 18 HD.
Step Six, fill in the last two CR with something cool. Phantom template, Monster of Legend, or even just 4 more HD. Whatever's appropriate.
The character will be named Demilich, and it'll be awesome.