Note: Dark lords are even more powerful than liches and should be used cautiously by the DM.
Let's use that bit above to guide us as we continue...
INTELLIGENCE: Exceptional to godlike
Lich is Int +2, Wis +2, Cha +2. Maybe +4 to each for these?
Natural armor seems a bit odd for this creature (although the somewhat similar blackball has high natural armor). A lich has a +5 natural armor bonus.
AKA spell resitance CR + 11.
A dark lord looks like the shadows of a person, but looks are deceiving. The monster is actually composed of material from the Negative Material Plane.
An interesting sidebar...
Manual of the Planes said:
In some locations on the Negative Energy Plane, the collapsing intensity of the plane is so great that the negative energy folds in on itself, stabilizing into solid chunks of utterly black matter. These chunks of voidstone might be the building blocks of such items as the sphere of annihilation. Indeed, anything that comes into contact with a voidstone is instantly destroyed. Unlike with a sphere of annihilation, a character touching a piece of voidstone gets a Fortitude saving throw (DC 25) each round he stays in contact with it. Even natives of the Negative Energy Plane are vulnerable to voidstones.
Maybe natural armor isn't so odd after all.
Combat: Any character who comes within 200’ of a dark lord is slowed due to the effects of heavy gravity (no save allowed).
Something like this?
Aura of Heavy Gravity (Su): A dark lord is continually surrounded by an aura of heavy gravity in a 200-foot-radius centered on itself. All creatures within the area are slowed (as the spell) while within the area and for x rounds after leaving the area, with no saving throw.
On each successful hit, a dark lord not only causes 1-12 points of damage, but drains one energy level if a save vs. death is failed. It also ages its victim 10d4 years if a saving throw vs. spells is failed. Both the energy drain and aging apply to each of the dark lord’s physical attacks. Thus, an unlucky character might lose two levels and age 80 years in one round.
"Voidstrike" (Su): The touch of a dark lord deals 1d12 points of negative energy damage and subjects the victim to its energy drain attack. Additionally, a successful hit prematurely ages the victim unless it succeeds on a DC x Fortitude save. This imposes a -4 penalty to Strength, Dexterity, and Constitution, and causes the victim's hair to turn white, skin to wrinkle, and posture to stoop. This effect is permanent and can only be removed by a break enchantment effect.
Energy Drain (Su): Living creatures hit by a dark lord's slam attack gain one negative level. The DC is x for the Fortitude save to remove a negative level. The save DC is Charisma-based. For each such negative level bestowed, the dark lord gains 5 temporary hit points.
In addition to its physical attacks, a dark lord can cast one spell per round. Consider the spell to be an innate power without the usual spell-casting requirements (e.g. no somatic gestures, incantations, or special components are needed). The dark lord has only nine spells that can be cast, but they are extremely powerful ones: disintegrate, duo-dimension, alter reality, reverse gravity, maze, astral spell, gate, imprisonment, and time stop.
At will (shudders) SLAs? Caster level equals HD?
A cleric of level 9-13 can turn a dark lord on a roll of 20. A cleric of level 14 + can turn a dark lord on a roll of 19-20.
A lich has +4 turn resistance. Maybe +6 or even +8 for dark lords?
A dark lord can be hit only by magical weapons with a +2 or greater bonus.
Lich's have damage reduction 15/bludgeoning and magic. Maybe 15/holy and magic?
The following spells, or attack forms, have no effect on dark lords: charm, sleep, enfeeblement, hold, cold, electricity, teleportation, polymorph, fear, magnetism, insanity, slow, disintegrate, maze, imprisonment, gravity, time, paralysis, or death (including poison).
How's this?
Immunities (Ex): Dark lords have immunity to cold, electricity, disintegration, polymorph (though they can use polymorph effects on themselves), and mind-affecting attacks. Additionally, they are immune to any temporal effects (such as haste, slow, or time stop), gravity effects (such as reverse gravity), or magnetism effects (such as a metalmaster's magnetism abilities or the magnetic attraction ability of a lodestone marauder).
Holy water will do only half normal damage on a dark lord.
Special ability?
A raise dead spell will destroy a dark lord, but it is allowed a saving throw versus spells.
Some special vulnerabilty to all life-restoring magic?
