Hows 20k sound for this beast?
[sblock="Gathra"]Gathra CR 12
LE Huge Magical Beast (Extraplanar)
Init -2; Senses Darkvision 60', low-light vision; Listen +9, Spot +9
AC 20, Touch 6, flat 20
hp 166 (12 hd), wp 60; DR 3/-, 10/magic
fort +18, Ref +5, Will +7
Spd 40'
Melee Gore +18 (1d10+12) and 2 Hooves +13 (1d6+6)
Trample 2d6+12 (AoO at -4 or Reflex DC 22 for half)
Space 15' (long); Reach 5'
BaB +12; Grp +24
Atk Options trample, bellow
S 35 D 7 C 30 I 4 W 17 C 16
Feats Cleave, Great Cleave, Improved Bull Rush, Power Attack, Awesome Blow
Skills Hide -5, Surival +9
Bellow (Sp) 3/day, fear, 30' radius, Will DC 18
Gathras are powerful and dangerous animals that wander the scorched plaines of Avernus. While they may look like herd animals, gathras are actually predators that hunt down and devour any animal unlucky enough to be caught in the open.
A gathra looks like a horrid blend of board and bull. It is heavily muscled, with stubby legs that can propel it at great speed. Two enormous tusks jut from it's fang-filled mouth, and it constantly drools as foul-smelling spittle. The eyes of a gathra glow with a dim, red light that becomes brighter when the beast is angered.
Demons and other evil creatures round up gathras to use them as mounts. The beasts are stubborn and unprdictable creatures that require constant discipline and domination to be kept in line.[/sblock]
Omega looks ok on a glance (I won't have time to do a proper review of these guys for a few days).
Just to make sure I got things right: An Ogre "pays" effectively two +1 boosts to get rid of a ECL +2, correct?
Yes.
However, I'm thinking of making the +1 racial bonuses back to +2, since the net gain on the Ogre is still higher than the 2 point loss.
Avalon:
Bad link. 
I'll have to look it over tomorrow.