What Jeremy said.
Loss of init + single BBEG vs. party of adventurers = dead BBEG. Your PCs probably could have taken out a 20th-level wizard lich (CR 22!) in the same round given adequate preparation.
In general, I do think that demons are slightly over-CRed. My solution is to rebalance the CR by advancing my standard demons 50%. This makes the average marilith CR 18, but with the following stats:
Marilith
Large Outsider (Chaotic, Evil)
Hit Dice: 13d8+65 (123 hp)
Initiative: +2 (Dex)
Speed: 40 ft.
AC: 29 (-1 size, +2 Dex, +18 natural)
Attacks: Weapon +17/+12/+7 melee, 5 weapons +17 melee, tail slam +15 melee
Damage: Weapon 1d8+5, weapons 1d8+2, tail slam 4d6+2
Face/Reach: 5 ft. by 5 ft./10 ft.
Special Attacks: Spell-like abilities, improved grab, constrict 4d6+7, summon demon
Special Qualities: Damage reduction 20/+2, SR 26, poison and electricity immunity, cold, fire, and acid resistance 20, telepathy
Saves: Fort +13, Ref +10, Will +12
Abilities: Str 21, Dex 15, Con 21, Int 18, Wis 18, Cha 16
Skills: Bluff +19, Concentration +20, Hide +15, Listen +28, Move Silently +17, Scry +19, Search +19, Sense Motive +20, Spellcraft +18, Spot +29
Feats: Cleave, Multiattack, Multidexterity, Multiweapon Fighting, Power Attack, Quicken Spell-Like Ability
Climate/Terrain: Any land and underground
Organization: Solitary or pair
Challenge Rating: 18
Treasure: Standard coins; double goods; standard items, plus 1d4 magic weapons
Alignment: Always chaotic evil
Advancement: 14-27 HD (Huge)
Spell-Like Abilities: At will-animate dead, bestow curse, chaos hammer, cloudkill, comprehend languages, darkness, desecrate, detect good, detect law, detect magic, inflict serious wounds, magic circle against good (self only), magic weapon, project image, polymorph self, pyrotechnics, see invisibility, shatter, telekinesis, teleport without error (self plus 50 pounds of objects only), unholy aura, and unholy blight. These abilities are as the spells cast by a 13th-level sorcerer (save DC 13 + spell level).
Improved Grab (Ex): To use this ability, the marilith must hit a Medium-size or smaller opponent with its tail slam attack. If it succeeds, it can constrict.
Constrict (Ex): A marilith deals 4d6+7 points of damage with a successful grapple check against Medium-size or smaller creatures. The constricted creature must succeed at a Fortitude save (DC 19) or lose consciousness for at long as it remains in the coils and for 2d4 rounds thereafter.
Summon Demon (Sp): Once per day a marilith can attempt to summon 4d10 dretches, 1d4 hezrou, or one nalfeshnee with a 50% chance of success, or one glabrezu or another marilith with a 20% chance of success.
Telepathy (Su): Mariliths can communicate telepathically with any creature within 100 feet that has a language.
Skills: Mariliths receive a +8 racial bonus to Listen and Spot checks.
Feats: A marilith receives the Multidexteriry and Multiweapon Fighting feats as bonus feats. In combination with its natural abilities, these feats allow the marilith to attack with all its arms at no penalty.
So, for a +1 CR increase, you get 38 additional hp, +4 to all attacks (and an extra iterative attack), +2 to saves, 48 (!) extra skill points, and another feat. Not bad, eh?
Of course, you could seriously abuse the advancement rules by giving the marilith one more hit die, and bumping its size to Huge, which grants ability score increases, better natural armor, and more reach for no additional CR increase.
Incidentally, I'd like to see demons in 3.5 acquire the See in Darkness supernatural ability that devils possess. With that ability, the marilith becomes positively horrendous, since it can cloak itself in darkness, gaining total concealment, and then project an image of itself to wreak havoc on the party.