The end type should be Outsider
The final level changes the creature's type to outsider, and from a strict rules-as-written perspective, that's all we need to care about. Savage species, where the 'type pyramid' is found, doesn't officially have the jurisdiction to impose that pyramid on The Forgotten Realms Campaign Setting, Players Guide to Faerun, etc, which are all the primary source for their own templates, and the Monster Manual is the primary source for how templates work in general. So, from a strict rules position, this type pyramid thing doesn't matter.
ALSO the pyramid doesn't matter, because it only governs (or pretends to govern) type changes based on templates, not any other source. Your 5th level class feature is not a template; the only template used herein is 'Lich'. So, even if you ignore the primary source rules and use the pyramid, this character is still an outsider.
If you instead wanted the character to be Undead, all you would need to do (regardless of type pyramid nonesense) is change the order in which the things are applied. Become a Lich after taking that last level, and you're Undead instead of Outsider. This is actually significantly more powerful, because then you are Undead (augmented outsider) instead of Outsider (augmented undead), which nets you the Undead traits with Outsider features (like better skill point stuff) v.s. Outsider traits with Undead features (like terrible BAB and saves coupled with no significant defenses).
Why does it matter if I'm Undead(augmented Outsider) or Outsider(augmented Undead)? What's the difference?
When you get a template, you gain the augmented subtype, which changes how things work for you a bit:
A creature with the augmented subtype usually has the traits of its current type, but the features of its original type.
Ok, so nothing is providing exception to this set up in our case, so lets look at what happens:
Undead says some stuff about hp, BAB, saves, and skill points. Then it says "These are features of the Undead type". That's how you know that they are features, not traits. Every type says this, though, and it's always BAB, saves, skill points, and HD size.
It also gives you a huge pile of immunities and special things and whatnot, and calls those traits. Those are the traits, not features, and they vary wildly by type beyond consistently telling you if something eats, breathes, and/or sleeps or not.
If you're an Outsider, but augmented Undead, you don't get the Outsider type's 8+int skill points and two free class skills and amazing saves and full BAB, and instead get the Undead type's terrible BAB, Will-only saves, 4+int skills, and its admittedly really-good d12 HD. You also don't get the Undead type's lack of a Con score, immunity to Fort save effects except ones that kill you dead, immunity to death from massive damage, weird resurrection stuff, being able to run forever without getting tired, etc. Instead you get proficiency with simple and martial weapons and that's about it. So one of these is kinda okay and one of them is ridiculously amazing.
Lastly, your type doesn't generally affect your ability to use your stuff unless that stuff depends on type, which the Lich's phylactery doesn't. Whether you are an Undead (augmented Outsider) or an Outsider (augmented Undead), your phylactery will still work.
While the Undead type has the massive drawback that you die when you are killed, the Outsider type has an only slightly less serious resurrection drawback, so that's not really a power consideration here.
But Lich takes care of some of that, right?
Yes, it does. The Lich template sets all current and future HD to d12s, and provides immunity to mind-affecting effects, and removes ones Constitution score. These things will still happen even if you're not Undead anymore, so long as you're a Lich (unless you get something that specifically changes this, like Polymorph Any Object specifying you gain a Con score, or another template changing your HD size again). It's still not nearly as good, barring very specific build situations, to be an Outsider(augmented Undead) as it is to be Undead(augmented Outsider). You're still missing out on tons of stuff.
Can I really even get Undead(augmented Outsider)? Wouldn't I need to settle for Undead(augmented Humanoid) or Outsider(augmented Undead) instead?
Yup! While the Lich template can only be applied to humanoids, you can take humanoid form with your 15 levels of Cleric of Cyric spellcasting as Polymorph Any Object is an 8th level trickery domain spell. If you didn't take trickery as one of your Cleric of Cyric domains (for shame!) then you would need a scroll of regular polymorph or similar. Either way, you can go back to being a humanoid in order to then become a lich and then end the polymorph effect.