Well, I once saw an encounter involving 3 elder para-elementals, each with 5 lvs of martial adept (each cr16, together EL19). The DM remarked that they seemed tougher than their cr let on, in that they were more than a match for a group of 6 ECL20 outsiders (it was a one-shot). Granted, we know that astral devas are weak for their ECL, but it seems to suggest that mid-cr monsters with a few lvs of martial adept can still make for challenging foes.
They could deal good damage, enough to get your players worrying but not quite enough to 1-shot them. They had excellent defenses (a lot of hp, fair AC, able to circumvent some popular attacks such as forcecage/maze and decent saves - not factoring in diamond mind).
The various MMs have a few high-cr melee foes. Have you ever tried those?
One problem I have is that I have a large group of PCs, so they have a very diverse ability to deal with foes - the have two melee tanks (dwarf fighter & goliath barbarian) and 3 "spell" casters in a cleric, sorcerer and psion. Plus, a rogue/spellthief and an elf paladin/fighter/champion of Corellon for finesse. Plus, an NPC cleric/paladin that can cause a lot of damage in melee as well and they recently had another high level fighter NPC for melee, too.
So, any single foe is not going to last in melee, but is also threatened at range as well. I was thinking of a dragon that continually hits & runs against them, but they could just teleport away to avoid the encounter (the psion & sorcerer both have teleport, and the cleric has a special teleport item) Unless I make it a psionic dragon & give it Trace Teleport... but, it's also why I'm considering the 3 spellcaster foes at once - a level 19/20 sorcerer, cleric and psion.