Ran an encounter with an oni (ogre mage) this weekend. Even with a half dozen support ghouls and ghasts, he was stomped before the end of his second turn. This was a five member 5th level party. A previous encounter with a single bullette tested the party to the max, and a fight with a group of 6 orc archers on the other side of a pit of 3 gelatinous cubes was a good challenge.
The difference was all in the terrain of the combat. The oni did enter combat invisible, but he quickly got surrounded. The party did so much damage so quickly (170+ points in one round), that it didn't matter if it had regeneration, spell-like abilities, or what.
So it was anti-climactic for me, but the players had fun stomping the BBEG of the campaign arc.
I had the PCs ambush an oni once, and a player critted him in the first round and killed him. It didn't even get to enter initiative. I was so sad.