I had always assumed binding a pit fiend, balor, or other big bad outsiders was possible due to the fact that they even have entries in the binding outsiders section. However, I've noticed that even such spells as Greater Binding & Ally both have a 18 HD cap, meaning that they can't summon & bind these creatures.
Is this a RAW mistake or does it just boil down to DM fiat for such instances in APs where they have been bound? Or is there some sort of spell/magic item combo that I'm missing?
Is it possible that those APs have used the binding spell, rather than the planar binding trio of spells? That spell has no HD-cap. Of course, it also doesn't have the same function.
Alternatively, they may have used the planar binding function of a gate spell, which has a HD limit for single creatures equal to your CL.
Or, you can go back to the old standby: it is a story element and has no basis in the rules. Anything is possible in 'story' and you are not required to create a rule so that players are able (or allowed) to replicate it. As an example: perhaps it is a month long binding ritual rather than a simple spell.
Or, IIRC, now with the mythic rules, the mythic versions of these spells have higher hd caps, thus letting mythic casters use greater planar ally/binding to get the job done.
Ah, looks like Gate and the mythic versions handle the job. Good to know and thanks all!