I'd like to propose that the paladin of tyranny (and maybe a paladin of slaughter) be a Tier 4 class instead of a Tier 5.
-Rebuke undead: They can pull off the same Command-an-undead-that-can-spawn-to-build-an-army trick that clerics and dread necros can
Possible, but of course they have half level, so half as much direct controlled. Also, I find the "spawn an army" trick rarely flies in most games, and I try to rank this off stuff that's legal and doesn't feel too gamey. Most DMs, I find, rule that the spawn themselves come out of your Rebuke pool (because you ARE controlling them, even if indirectly, through Rebuke Undead) so extra ones become uncontrolled. Now, you can still pull the Rod of Defiance/Lyre of the Restful Soul trick, but it's not as good. Still, this can be quite useful, if nothing else by rebuking a Ghostly Visage given the chance.
-Deadly touch: A potentially high damage touch attack (easly 200+ hps at level 20).
I rarely see PoTs maxing Charisma enough to have a Charisma of 30. Possible sure, but "easily" is a bit of a stretch. They have MAD (needing Str for combat, Con for hitpoints, Wis for casting, and Charisma for a number of their abilities) and they can't dump Dex too much, so I don't see them successfully pumping their Charisma like that. I think a Charisma of 20 is far more likely. Handy sure, but not THAT incredible.
-Aura of Dispair (PoT only): Good and easy debuff
Yes, and hilarious when combined with Hexblade 4 with the Dark Companion substitution, and perhaps Bind Vestige/Improved Bind Vestige for Foculor's Aura of Sadness. -6 to saves is great for your party casters. The PoT/Hexblade in my group is pulling this stunt in a party with a Dread Necromancer right now, and yes, it's kinda obscene. So I definitely give you this point.
And they can do all of this while pulling off the same tricks a regular paladin can like battle blessing, divine feats, and DMM feats.
I've found that Paladins rarely go for DMM, as their buff aren't nearly as good and they need the feats. Battle Blessing is cool, that I'll grant you.
I dunno. I'm up in the air about Paladins being Tier 4 or 5 (especially since they also have Diplomacy as a class skill with some Charisma synergy), so I'm certainly considering your points, but I've just never seen a Paladin really take off like, for example, a Barbarian might. Their penalties (MAD, conduct codes) seem to hit them hard, negating a lot of their advantages.
I do agree though that Paladins of Tyranny seem to be the strongest Paladin varient, mostly for that save debuff aura.
JaronK