Divinations to find out who and what the party are, then send in the small band of effective goons to knock out this specific threat.
Demons.
Spiders.
Undead.
Drow hit squad.
Slave servitor hit squads.
I would think something incorporeal that goes straight to draining mental stats, something large brute monsters won't have a lot of.
A 12 HD advanced allip sounds about right for that type of thing. Wisdom touch drain and will save effects. Taking the spring attack chain is a nice way to go for flying incorps.
The lich has one (or a whole chorus of them) she specially made using creatures swaddled so they can't be ID'd to torment the undead while living. She then makes it(them) think the party tormented it(them) in life and unleashes the undead horror.
Allip click to see monster
Size/Type: Medium Undead (Incorporeal)
Hit Dice: 4d12 (26 hp)
Initiative: +5
Speed: Fly 30 ft. (perfect) (6 squares)
Armor Class: 15 (+1 Dex, +4 deflection), touch 15, flat-footed 14
Base Attack/Grapple: +2/—
Attack: Incorporeal touch +3 melee (1d4 Wisdom drain)
Full Attack: Incorporeal touch +3 melee (1d4 Wisdom drain)
Space/Reach: 5 ft./5 ft.
Special Attacks: Babble, madness, Wisdom drain
Special Qualities: Darkvision 60 ft., incorporeal traits, +2 turn resistance, undead traits
Saves: Fort +1, Ref +4, Will +4
Abilities: Str Ø, Dex 12, Con Ø, Int 11, Wis 11, Cha 18
Skills: Hide +8, Intimidate +7, Listen +7, Search +4, Spot +7, Survival +0 (+2 following tracks)
Feats: Improved Initiative, Lightning Reflexes
Environment: Any
Organization: Solitary
Challenge Rating: 3
Treasure: None
Alignment: Always neutral evil
Advancement: 5-12 HD (Medium)
Level Adjustment: —
An allip is the spectral remains of someone driven to suicide by a madness that afflicted it in life. It craves only revenge and unrelentingly pursues those who tormented it in life and pushed it over the brink.
An allip cannot speak intelligibly.
Combat
An allip is unable to cause physical harm, although it doesn’t appear to know that. It keeps flailing away at enemies, yet it inflicts no wounds.
Babble (Su)
An allip constantly mutters and whines to itself, creating a hypnotic effect. All sane creatures within 60 feet of the allip must succeed on a DC 16 Will save or be affected as though by a hypnotism spell for 2d4 rounds. This is a sonic mind-affecting compulsion effect.
Creatures that successfully save cannot be affected by the same allip’s babble for 24 hours. The save DC is Charisma-based.
Madness (Su)
Anyone targeting an allip with a thought detection, mind control, or telepathic ability makes direct contact with its tortured mind and takes 1d4 points of Wisdom damage.
Wisdom Drain (Su)
An allip causes 1d4 points of Wisdom drain each time it hits with its incorporeal touch attack. On each such successful attack, it gains 5 temporary hit points.