I like the realism argument. 'It was a gryphon. Why would a gryphon have loot. Feel free to loot the twigs from the nest it slept in, and the crushed/broken feathers/excrement..' 'The last gryphon had loot...' 'No, that was the corpse of an adventurer who died trying to kill the gryphon. Feel free to search the area for corpses.'
Omar-Akheg, Challenger of Warriors
Size/Type: Medium Undead [Augmented Humanoid]
Hit Dice: 22d12+44 (178)
Initiative: +7
Speed: 30 ft. (6 squares), swim 60 ft.
Armor Class: 30 (+10 +2 black Full-Plate, +1 Dex, +4 natural, +2 deflection (Shield of Faith), +3 deflection (cloak of flame)), touch 16, flat-footed 15
Base Attack/Grapple: +11/+17
Attack: Bone Greatsword of Blood-Draining (single handed) +16 melee (2d6+6+1d6 fire and 1 negative level (DC 16 negates)) or bite +14 melee (1d8+3+1d6 fire) or throw flames +13 ranged (2d6+4 fire + DC 15 reflex or catch on fire)
Full Attack: Bone Greatsword of Blood-Draining (single handed) +16/+11/+6 melee (2d6+6+1d6 fire and 1 negative level (DC 16 negates)) and bite +14 melee (1d8+3+1d6 fire) and snaking vertebrae +16 melee (1d4 dex damage (fort DC 17 negates)) and throw flames +13 ranged (2d6+4 fire + DC 15 reflex or catch on fire) (needs one free hand)
Space/Reach: 5 ft./15 ft.
Special Attacks: Blood frenzy, energy drain, throw flame, scream of blood, snaking vertebrae, danse macabre
Special Qualities: Blindsense 30 ft., darkvision 60 ft., light blindness, speak with sharks, reaving aura, aura of terror, subjective gravity, cloak of flames, bone blade, ignore the weak, turn resistance +4, SLAs, evasion, uncanny dodge, DR 10/Good and Silver, Fast Healing 5
Saves: Fort +13, Ref +18, Will +17
Abilities: Str 22, Dex 18, Con 0, Int 13, Wis 16, Cha 21
Skills: Balance +12*, Hide +21*, Listen +11*, Profession (hunter) +8*, Track +11*, Ride +17, Spot +11*, Survival +7*, Spellcraft +15, Intimidate +22, Sense Motive +15
Feats: Improved Initiative, Ability Focus (Reaving Aura), Lifesense, Vatic Gaze, Power Attack, Cleave, Improved Sunder, Improved Bull-Rush, Combat Brute, Shock Trooper, Sweeping Advance, Bonecrafting, Willing Deformity, Extend Reach, Inhuman Reach, Disciple of Darkness, Hellbound Knight, Combat Expertise, Dodge, Mobility, Spring Attack, Bounding Assault, Whirlwind Attack, Improved Whirlwind Attack, Martial Study: [Iron Heart Surge], Martial Stance: [Absolute Steel Stance], Monkey Grip
Environment: Everywhere
Organization: Solitary, pair, team (5-8), patrol (11-20 plus 1 3rd-level lieutenant and 1-2 sharks), band (20-80 plus 100% noncombatants plus 1 3rd-level lieutenant and 1 4th-level chieftain per 20 adults plus 1-2 sharks), or tribe (70-160 plus 100% noncombatants plus 1 3rd-level lieutenant per 20 adults, 1 4th-level chieftain per 40 adults, 9 4th-level guards, 1-4 underpriestesses of 3rd-6th level, 1 7th-level priestess, and 1 baron of 6th-8th level plus 5-8 sharks)
Challenge Rating: 12
Treasure: Gear and one major magical item located inside the chest cavity
Alignment: Usually lawful evil
Advancement: 23-28 HD (Medium), 29-36 HD (Large), or by character class
Level Adjustment: +10
This dark-armoured warrior wears the skin of his flayed face stretched across a rotting skull, flame leaps from where his eyes used to be, and darkness rushes up the passageway behind him as he screams a challenge at you, rushing forward far faster than his undead frame would suggest he could move.
Called the akwarazim, the Knights of Hell who served Orcus during the latter's ill-fortuned ascent to godhood universally channeled a fragment of a god's power and had it stripped from them, a process that drove them insane even as it turned them into insanely powerful undead. Several attempts have been made by agents of the good gods to track them down and put an end to them, but their ability to shift between planes has made such attempts fruitless.
Blood Frenzy (Ex): Every time the akwarazim is wounded or wounds another person, they or the akwarazim have a chance to enter a blood frenzy, a state in which the afflicted character gains +4 str and +4 constitution but strikes out blindly at the closest nearby creature (roll randomly if creatures are equally close) until they either make a save or are knocked out. Bloody Frenzy is a mind-affecting effect. DC 17 fort save to not enter the frenzy.
Energy Drain (Su): The akwarazim has a chance of applying a negative level when he hits with his bite attack or his Bone greatsword. The character struck can avoid this effect with a DC 16 Fortitude save(this save is Cha-based). The akwarazim gains 5 temporary hp (that stack up to 100 thp) each time he delivers a negative level to an opponent.
Scream of Blood (Su): Once every 1d4 rounds as a full-round action, the akwarazim can scream in torment, conjuring forth a torrent of blood in a 30' cone. All characters in the cone must make a DC 17 reflex save or be swept 2d6 squares away from the akwarazim, knocked prone, and take 2d6 bludgeoning damage. The affected squares are covered in a blood slick that makes movement difficult - they now and for the next 10 minutes count as difficult terrain and require a balance check to move across similar to the grease spell.
Snaking Vertebrae (Ex): When the akwarazim performs a full attack, vertebrae extend from his wrists, dripping with poison, and strike his attackee. If they hit, they do 1 pt of dmg and inject the attackee with poison, fort save DC 17, 1d4 dex/1d4 dex, cumulative poisonings of this poison stack.
Reaving Aura (Ex): The akwarazim is surrounded by an aura of negative energy that rips life force from his foes. Any time the akwarazim kills a foe, he heals 15 hitpoints of damage. Also, any living creature within 30' of the akwarazim when the akwarazim's turn begins, takes 1 pt of negative energy damage, and the akwarazim heals 1 hitpoint.
Cloak of Flames (Su): Any creature striking the akwarazim takes 2d6 points of fire damage. Anything within 5' of the akwarazim, ditto. Things burst into flame near the akwarazim, and water boils. The akwarazim's attacks do an extra 1d6 fire damage.
Aura of Fear (Ex): Any creature that meets the akwarazim's gaze must make an immediate DC 17 Will save or become Panicked for 1d4 rounds. If you succeed on this save, you are still Shaken for 1d4 rounds. Multiple uses of this Gaze attack stack, and you do not become immune to it after succeeding on a save.
Subjective Gravity (Su): The akwarazim can decide which direction is 'down' for it at any time during it's action as a free action. As falling is a free action, it can potentially get free movement out of this ability. It also always lands on it's feet if it falls in a direction. This ability counters and dispels any ability which would suspend the akwarazim in midair or forcefully change the way gravity affects it.
Bone Blade (Ex): At any time the akwarazim may remove any of it's bones from inside it's rotting body, and use them as if they were a +1 Bone Greatsword of Blood Draining. In all other hands, they remain regular bones.
Ignore the Weak (Su): If an enemy has a strength score of less than 14, if they use a spell or ability or attack that in some way affects an akwarazim, the akwarazim may choose to attempt to ignore it. There is a 50% chance that they successfully do so.
Danse Macabre (Ex): As a full-round action, all corpses within 100' of the akwarazim animate as zombies. They obey the akwarazim's orders to the best of their abilities, but de-animate relatively quickly (10 rounds). As the akwarazim are insane, they usually don't stockpile awesome corpses to turn into zombies if they are attacked. Also, the ability will not animate more than 88 HD of corpses.
SLAs: at will/ darkness, unhallow, planeshift 3/day deeper darkness, desecrate, meld with stone 1/day dimension door, tidal surge(comes with free compulsory random planeshift)
This is a single monster that would challenge and terrify your PC's. I just came up with it in about ten minutes. With a big encounter, with BFC, damage, blockers.. all that good shit.. you should have no trouble making stuff that challenges your PCs. Even if they all have leadership. Even if their feats and gear are way more optimised than their classes/races.
Also, by the way? Spot gets a -1 for each ten feet away from the hidden thing. And you don't get a cleave for popping a mirror image. You didn't actually hit anything. You whiffed air.
EDIT: Also, saying yes to leadership once ! = saying yes to leadership forever. 'No, I liked bob's idea, it was really flavoursome, but now the party is bigger and you just want a second character to buff your fighter..so... no.'
As an example of the kind of big encounter i'm talking about, how about this;
Hobgoblin fighter 4's riding giant flyby attack eagles in a massive cavern covered in sinkhole/geysers that shoot steam on a random rotation (DC 25 int check to work it out and be able to tell what's going to go off next) with a strike team of tower shield/full plate wearing salamander nobility using molotov cocktails and flaming spears and iron nets to slow down the PCs, massed ranks of hobgoblin archers using ranged net volleys and catapults (reflex DC = artillery commander's profession: siege engineer check.. crank that motherfucker) firing rains of sulphur and caltrops and ball bearings... have batteries of volleying hobgoblin archers with marshals and bards buffing them, and then when they break through to the ranged have a couple of armoured elephants come bursting in through big doors and start trampling shit while guys on their backs hurl tanglefoot bags around. For doubleplusfun, throw in a shaman with BFC spells and to make places difficult terrain.
Go for some old DnD classics like endless hordes of spawning undead, or deadly trap-rooms... hell, if you're feeling vindictive, get out grimtooth's...