It sounds like Oddysey and her crew had a fun time with an overpowered foe that was far beyond the the usual limits of level-appropriate encounters. I'm no fan of level-appropriate foes. Enemies you can expect to defeat don't inspire good gaming. They just encourage bare-bones grinding combat.
Pulling off a successful above-level-appropriate encounter requires you to be flexible and to give the players a chance to understand just how deep in over their heads they are before the hammer falls. Those are what separate a good DM from a killer DM in old school and neo-classical gaming. The PCs should have multiple avenues of survival, if not actual victory.
Once you've got that down, however, there's all sorts of variations on the theme of the portal guardian Odyssey used. Here are two of my favorites:
Things in the Walls
The PCs know there's something nasty stalking them. They know they can't take it (them?) in a fair fight. And they can't see it.
That last is key. You're playing on popular horror movie tropes here. The thing is nearby, but you can't see it. You can sense it, though. You can feel the chill in the air that happens whenever they are close, or the distinctive smell, or you can hear them scratch-scratch-scratching in the walls.
This works best in a complex terrain that allows lots of movement, chasing, doubling back, and maneuver. Places like haunted houses, warehouses, mazes, and catacombs. I prefer to use just one big monster for this sort of thing, as using lots of little guys can devolve into a drawn-out cat-and-mouse thing where the PCs work to isolate them in small enough groups to defeat. That looks cool on paper, but can easily eat up an entire evening's worth of gaming. Having just one or two big nasties is much more manageable.
Deal with the Devil
The players know the guardian is nasty. So nasty that even using their best tricks, the odds say at least one hero will die to defeat it. The guardian must be defeated or the quest is lost. However, there is a way to neutralize the guardian that doesn't require anyone dying. And it'll only cost you...
This one's great for the roleplaying value, but can be difficult to pull off. The players will look, and look hard, for another way around, and if you're too blatant about shutting down their attempts, they'll get justifiably annoyed at your railroading. The way I usually set this up is to make the offer non-event specific. That is, I have a powerful but scary NPC tell one or more of the PCs, “Hey, if you ever run into something you can't defeat, or a problem you can't crack, you can buy this get-out-of-jail-free card. And it'll only cost you...”
And I leave it there on the table, tempting them. Eventually, they'll face a problem that their collective ingenuity isn't overcoming. And there the offer will be, tempting them.
Photo credits: vintagedept, geishaboy500.