This answer addresses fundamental problems which lead to GMs having problems such as what you stated. The following is a summary:
- Balanced PCs make it easier to create challenges.
- There are a number of mechanics in the game that are rarely utilized which can make this easier for you.
- Time and resource management are fundamental tools of the GM to create challenges, and create dramatic tension.
- Consider the odds that a single Dominate power will work on an evenly balanced challenge vs a demon.
- Consider precisely how the various mechanics work.
I will begin the answer with a discussion on Psions vs Wizards. Why? Understanding those two classes is fundamental to creating mid to high level challenges. It also creates an appreciation for the problems that each respective class goes through.
Modifying the rule system to counter their domination is unnecessary. Why?
My first justification for this view is that the Psion (or Wizard) is using up resources in order to cast Domination. Thus, so long as time and resources matter in your campaign, then the spells/psionics are balanced against this fact.
My second justification for this view is that Psions are typically limited in the number of powers they possess. This is a signature ability of the class - i.e, the player's time to shine.
Thirdly, lets consider the differences between Psion and Wizard in this very specific regard. The Psion has the ability to Dominate Monster earlier than a Wizard (Wizard Level 18 vs Psion Level 11). But the Psion's Dominate is limited in power, and gradually grows stronger.
I highly suggest gaining a detailed understanding of the way Psionics works.
The variables of a power’s effect often depend on its manifester level, which is equal to your psionic class level. A power that can be augmented for additional effect is also limited by your manifester level (you can’t spend more power points on a power than your manifester level) - d20srd.org
What does this mean? It means that Dominating an Outsider is something that the Psion has recently achieved - since you stated that the Psion is 11th level. It is equivalent to (in terms of resource cost and limitation of access) the most intense power the character can possibly manifest.
Another consequence of this is that the Psion's duration has tactical implications.
If you spend 1 additional power point, this power’s duration is 1 hour rather than concentration. If you spend 2 additional power points, this power’s duration is 1 day rather than concentration. If you spend 4 additional power points, this power’s duration is 1 day per manifester level rather than concentration. - d20srd.org
The Psion is unable to increase the duration at Level 11 with Dominate when dominating an Outsider. So yes, the Wizard gets it later. But the Psionic version has weaknesses.
Given that he is Level 11. Let us assume he started with INT 18. Maybe +2 from Race (this information wasnt given in the question). +2 INT from Levels. Perhaps +2 INT from items. Then his INT is 24. So his PP is 106+132. (Maybe less if he has no racial bonus, in that case 106+121).
Most intelligent demons have Dispel Magic. This can tear away at the magical defences of the players - thus posing an increased resource cost on them. Indiscriminate bombardment of Dispell Magic (which many demons have free access to) can cause problems for the PCs.
The spells necessary to hold a Demon in place are another resource cost on the players.
Alot of problems with regards to creating challenges for the players, such as what you stated, stem from the fact Magic Item rules are not used properly. Remember that +4 ability score boosting items are balanced for Level 14 characters. See Magic Item Compendium Page 226.
If you tone down the items, then the encounters become more statistically challenging.
"In general, PCs should own items of their own character level or lower." - magic item compendium
The other two limitations to magic items are:
Where do you acquire it? Settlements have gp limitations which is actually a significant problem when it comes to acquiring new magical items.
Secondly, only a certain % of your wealth can be spent on a single item at character creation.
Thirdly, the chance of acquiring a vast array of ability score boosting items using the existing treasure tables is pretty low. Possible. But low. If you have been allowing the Players to treat the magic item lists as shopping lists, then creating challenges will be harder for you.
So, there are a number of mechanics in the game that tone down the PCs and are often forgotten by GMs and Players. So if you are having problems with PCs just brute forcing their way through problems, looking at the existing mechanics such as these may tone down that strategy.
“You know what the subject is experiencing, but you do not receive direct sensory input from it, nor can it communicate with you telepathically.” - d20srd
It is a demon. It chews out its own tongue. Its not really explicitly stated in the game that you need a tongue to speak. Common sense ruling allows it, however.
“They ask who it’s master is.” - problem with Domination
The demon only knows the subordinate master that communicates to it.
If the demon is of any importance, higher up demons might have tampered with its memory, or flat out bluffed the crap out of it.
“full sensory input as interpreted by the mind of the subject” - d20srd.org
Point 1 - Ad hoc: Even comprehending the mind of the demon could be subject the caster to madness checks.
Point 2 - The demon’s mind is insane. He interprets in messed up ways. He sees conspiracies where there are none, insults where none exist, paranoid of being betrayed by higher ups. All the speculations could throw the players in a loop. Effectively, the demon is not human, so dont answer questions from a human perspective. Answer them from a more eternal, infernal, perspective.
“Subjects resist this control, and any subject forced to take actions against its nature receives a new saving throw with a +2 bonus.” - d20srd.org
Speaking honestly could be argued to be against its nature. In fact, there are so many ways one could infer this for a demon. Thus, this could chunk a good amount of resources from the Psion, depending on dice rolls.
“Once control is established, the range at which it can be exercised is unlimited, as long as you and the subject are on the same plane.” - d20srd.org
If the demon is important, it could be watched by Clairvoyance. Such a caster/demon might interfere - perhaps send reinforcements, or teleport the demon to a different plane (if possible).
Depending on how you interpret Intelligence ability score in D&D (there are many schools of thought on this topic, which I will not go into), you could argue that its superiors simply don’t give it sophisticated information related to their strategy.
Genius demons will create genius tier plans. It is not within its ability of the lowly demon to grasp plans of machiavellian complexity which is dependent on an understanding of fuzzy logic or chaos theory, and the psychology of individual humans and large groups. The motto: Plans within plans, applies here.
The typical Balor is smarter than almost every Human (other than the most experienced Wizards and a select few other peoples).
If you wish further inspiration with these ideas, I suggest looking into Frank Herbert's Dune. Remember, the very nature of the plot and conspiracy can be the challenge. It does not necessarily need to be a challenge that can be solved with dice rolls.
Another source of influence is Fiendish Codex I: Hordes of the Abyss. There are a ton of ideas there.
The Nightmare spell (see d20srd.org). By the book it applies to arcane spell casters. So, if you are using the standard rule that "psionics is NOT different", then it could apply. It is reasonable to think so. Why should nightmares affect a Wizard but not a Psion?
Let us assume the Demon is a Hezrou (with CR 11, so a fair challenge for the party). Its base Will Save is +9. If you believe that being honest about anything is against its nature, then its will save is +11. If you restricted magic items, then the DC of the dominate will be:
A saving throw against your power has a DC 10 + the level of the power + your key ability modifier (Intelligence for a psion, Wisdom for a psychic warrior, or Charisma for a wilder). A power’s level can vary depending on your class.
In addition, for every 2 additional power points you spend to achieve any of these effects, this power’s save DC increases by 1.
So DC 21 (10 base, +7 from INT, +2 from augment, +2 from psionic focus and greater psionic focus).
So, Dominate has a roughly 50:50 shot of working on it. However...
If your power is being resisted by a creature with power resistance, you must make a manifester level check (d20 + manifester level) at least equal to the creature’s power resistance for the power to affect that creature.
The Hezrou has a SR of 19. So typically this means there is a 30-40% chance of failure due to this. Alot of GMs forget to use Spell Resistance / Power Resistance.
Also... this does not take into account the number of ways in which a Hezrou can force Concentration checks.
So, the chance of a single Domination working to solve the challenge is low! Very very low considering the potential forced re-rolls!
A possible challenge: Understanding its true nature, and carefully constructing commands so as to not go against its nature adds to the challenge (and provides a mechanical reward in the form of spells succeeding more and with less forced re-rolls)