If I wanted to make the ogre mage worth its cr, I would probably give it 3 more HD and replace its SLAs with wizard9 spellcasting or something.
But then it may lose some of its uniqueness as it then becomes just another spellcaster with more hp.
And while we're talking inappropriate CRs - what about the mountain giant from MM II? CR 26! Really? I think a single 26th level character would mop the floor with said giant. CR 15 looks more favorable to me.
Worse, it has a will save of only +10, so any wizard can easily dominate it and be on his way. And we all know that huge brutish foes tend to have crap will saves, so I won't really call it meta-gaming. I agree with cr15-16 tops. At any rate, the tarrasque seems more threatening than it.
For my submission, i recommend the Remorhaz as a being under-CR. I didn't fathom it in 3.0, and they didn't really change anything going to 3.5, so apparently WotC REALLY thinks that's a fair challenge for a level 7 party.
It is "fair" if you can accept that "expends 25% of the party's resources" means losing 1 PC, since that is typically what will happen (remorhaz springs out of the ice, swallows whole a PC, the rest of the party focus-fires on it while the fighter melts inside).
On my part, I feel the digestor does not warrant its cr6. It has no real attacks beyond its acid spray which doesn't really deal that much damage either.
I dunno about the tarrasque being cr20 either. I have heard about parties as low as lv14 taking it down.
Also, while not necessarily under-cr'ed, I do feel that a few spellcasting-type monsters, such as the nymph and ghaele are too fragile to warrant so high crs. Unless they are supported adequately with tanks, they will likely go down too quickly in combat before they can utilize their powers.