Planar Binding is pretty rough.
It can be made less broken if you actually force the spellcaster to bargain with the spirit he summons. It doesn't hurt to tweak the spell so that it depends not on HD but CR so that the caster can't abuse low HD high magic creatures.
Most of the problems I see with the spell usage described by other DMs come from what I see as the DM being overgenerous with the idea that the creature doesn't mind being summoned and is eager or willing to help. Compelling the creature to give you wishes would pretty much count as 'unreasonable service', and even if the creature was willing you'd almost certainly be dealing with 'monkey's paw wishes' from the compelled creature.
A common use of the spell is to summon Imps for their Commune ability, which more or less gets you access to pertinent information regarding anything. This can trivialize many non-combat scenarios.
So, you ask a devious fiend to commune with some outer planar being on your behalf (presumably a greater devil of some sort), and that outer planar being is itself likely manipulate the truth and the fiend who is so compelled is likely to lie or withhold critical information from the answer, and you think that this trivializes the situation?
Summon a Glabrezu and take his monthly Wish spell.
Unreasonable service. The Glabrezu would likely outright refuse and be within the wording of the spell to do so. And if he doesn't, heaven help you (literally) from the results of a wish compelled unwillingly from a fiend. Talk about something likely to twist the wording of the spell - the DM woudln't even be being much of a RBDM to do so in that case.
So, right before that, if your party can't kill a CR13, summon an Archon and request he help you with your next encounter against a demon or devil, something they're happy to do (so it should succeed).
So you think Archons are completely happy to help a diabolist consort with fiends? Especially those that do things like the following...
Bind a Succubus and have her seduce the local King/Lord/Magistrate/High Priest and you have blackmail against them, which again can trivialize a lot of non-combat encounters.
First of all, how in the world do you think society treats a diabolist that summons up fiends to seduce soveriegn monarchs? Second of all, how long do you think a society would last if they didn't take protections from this vary obvious thing? Do you think your character is the very first wizard/cleric to ever think, "Gee, I can get phenomenal power by summoning up a fiend! I could even mind-control the King, forcing everyone to obey my commands!" I mean that's 'Evil Plot 101', and like Paul Maud'Dib learned dozens of words for poisons and how to avoid them and never ate without a poison sniffer hovering over his food, in a world with Planar Binding you can believe that the sovereigns wouldn't go anywhere without at least some sort of 'Protection from X' about their person.
Summon an Efreeti for unlimited wishes for only a 6th level spell at no real cost to the player.
Again, unreasonable command or service, and any DM that let's a player compell wishes from an unwilling creature bound only by a non-permenent spell without twisting every letter of the wish is getting what they deserve. At the very least, we are talking about winning a difficult resisted charisma check.
Take a piece of it's flesh before it leaves, make a simulacrum of it, and you've got three wishes every day for the rest of your career.
I'm not sure that I agree that an illusionary Efreeti with half normal HD retains 'grant wishes' as a power appropriate to its new HD. I'm not even sure any spell-casting ability is appropriate, but at the very least its new caster level ought to be half (6th in this case) and any spells not normally castable by a 6th level caster ought to be reevaluated. Very generously, I
might consider limited wish a possibility here, but even more likely I might tell you that the thing is an illusion and granting wishes is now bloody well beyond its new power.
Erinyes have always-on True Seeing. Lillends have Identify. Planetar casts Raise Dead.
That's more like it. Those are the sort of bargains I can imagine the beings entering into, though you'd probably be better off with some sort of bribe in each case.
Seriously, the spell description requires the DM to use judgment. The DM must assign difficulties, must RP out the being according to its wishes and desires, and must decide what is 'unreasonable'. If the DM doesn't excercise judgment like that, then you can't blame the spell (entirely) for it being broken in application.