I'm beginning to run into this problem with my 10th level gestalt party. I was doing a great job of challenging them to the breaking point all the way up to about 9th level. I use a lot of tanarukk and trolls (of various varieties), and by that point they'd gotten good at hitting with fire and acid, or at least incapacitating the trolls until they could get around to burning them, etc.
9th level is also when my Druid//Sorcerer player picked up Arcane Strike. Drop a 4th level spell, pounce in tiger form (with Girallon's Blessing) and get +4 attack/+4d4 damage to each of seven attacks.
The other thing I've noticed is that many creatures have relatively low AC for their CR. Even CR 10 critters often only have an AC of 20 or maybe 23. When my Barb//Beguiler lays down haste and rages, he's at something like +20/+20/+15 to hit (and he doesn't have power attack to dump any of that BAB into). At 12th level he'll also pick up Arcane Strike.
The other thing is that they will often "jump to the end" by flying over things (took me a bit to realize to expect that...), and they will spam invisibility/invisibility sphere on the whole party, silence themselves, and they've now started casting remove scent, so the trolls have no chance to notice them until the Druid (and his tiger animal companion) pounces from invisibility. I've started giving the trolls Large and In Charge (Draconomicon) to counter that somewhat, but it doesn't do any good in the surprise round.
Also, my Druid//Sorcerer has an impressive AC at ~27 with greater mage armor, barkskin, plus the base AC of his wildshape forms (favorite is a Red Tiger [Silver Marches])
The one thing that just baffled the hell out of them (and I could have slowly obliterated them, as they were running low on spells, if I'd been mean) was a Shadow Creature Red Abishai (with Mindsight) during polar night. I think often times outsiders, dragons, and enemy casters are about the only thing that will challenge such high-level characters.
We'll see how tonight goes, though. My 10th level PC's (4 of them, plus one Druid//Scout/Wiz DMPC) will try to hunt down a gestalt CR 11, 16 HD fiendish rage drake. I swapped Improved Crit for Blindfight, and gave it Leap Attack with its 15th HD. Depending on how they attempt to engage it, a slim possibility exists I could kill one of my PC's outright on the first pounce. (Charging, four attacks at +22 [1d8+20] and a bite at +17 [2d6+15, plus Imp Grab, then a Fort save DC 27 or stunned]) That's a minimum of 101 points of damage if all attacks hit. (Because of blind fight, he'll have ~75% chance of any attack getting past the miss chance from invisibility).
I know my Barb/Beguiler has ~120 hp. But my Rogue/Wiz only has about 70...