Because Inevitability just can't catch a break.
Nightmares are Large evil outsiders with 6 HD. Their chassis is pretty good: the physical stats one would expect of a fiendish horse combined with above-average mentals. Nightmares have three natural attacks: two hooves and a bite (all sadly without reach). The hooves also deal 1d4 fire damage, the bite is best used on a mouthpick. They have excellent natural armor, and a body shape it's still possible to find physical armor for. Also, they're one of the few creatures that can UMD Horseshoes of Flame and not look ridiculous. Amusingly enough, nightmares are slower on land than any kind of PHB horse: at most they'll be able to keep up with a pony. The 90 ft. fly speed makes up for that, though.
Furthermore, there's the Smoke ability. A debuffing cone that takes only a free action to use and lasts for minutes may seem good, but it's non-friendly: think carefully before using it. The same ability also gives nightmares (total) concealment against attacks without concealing its opponents from it, which is very good for obvious reasons.
Finally, nightmares get CL 20 Astral Projection and Etherealness at-will. How balanced.
Etherealness alone is highly valuable when it comes to avoiding encounters, scouting, and general exploration, and its CL is high enough to let you take the party, the wizard's familiar, the paladin's mount, and the random goblin your rogue wanted to rise as a pet all with you. It's also a standard action. That said, it's not like the ability is completely unrateable: we've had creatures with similar powers before.
Astral Projection is even worse, though. It's an improved version of the astral projection the tier 1 casters will have at level 17, because it doesn't require expensive components to use and can arguably be used as a standard action. It is this ability that makes me assign an asterisk here, while also discounting this ability while assigning a LA.
Etherealness for the entire party is still overpowered, but at least manageably so now. I think a LA of +2* fits well enough: please do discuss.
At least this was easy: Astral Projection and Etherealness are less impressive when casters get them in two levels (or earlier, with planar binding and friends), and advancing a monster by 9 RHD has never made it worth nine extra levels. -0* LA.
Next are nightshades!