This is an interesting problem, that I've run into a few times but haven't solved yet. Here's some of my observations on it, in case they help.
The first thing to understand is that you can't do this without Deus Ex Machina. The "rules" that are established in most campaigns are that antagonists will press an advantage as long as they have the upper hand, and that characters below zero hit points who are left unattended perish. Any sudden deviation from that expected model will be Deus Ex Machina, by definition.
What's needed here is a way to make the DEM grate a bit less on the players.
Telling the Players
Your first consideration is whether or not to tell the rest of the group what happened. If you do, I'd recommend just asking to rewind time and start the encounter over (in a more balanced form). This erases it from the "story," and puts a more mechanical spin on the "saving." However, some groups are very set against this. It also means you have to redesign encounter components that rely on trickery.
If you don't think you're going to get a lot of mileage out of admitting your mistake to the group, or if you're dead set on digging yourself out of the problem in a continuous narrative, keep your mouth shut. Telling the players that you're actively working to save them does nothing more than shine a colossal spotlight on your DEM, making its faults stand out.
Obvious Outs
Sometimes you get very lucky, and the creature in question has a known "out" for overly tough encounters (such as dragging victims back to a cave to be dined on later). It doesn't happen often, but it's worth checking on. It'll still feel like DEM, but at least you'll have something in print to say "no, really guys. That's how it's supposed to work."
Death is Only the Beginning
Continuing the campaign after the point of death (as suggested by Sardathrion) can work really well. In this case the DEM is a necessary contrivance to get access to a novel campaign, a price many players are willing to pay.
The problem is that you're effectively starting a new campaign from scratch. Everything that's been prepared so far is put on the back-burner while the players deal with their after life.
The other issue you need to deal with is establishing whether the players are exploring this new world, or working to get back to the old one.
This was actually the basis of one of my favorite D&D campaigns to play in. The players wiped fairly early on, and "woke up" standing in line to the afterlife. Players being players, everyone escaped the line, met up, and continued the campaign (which now had a Planescape focus).
Introduce New Plot Points
You can introduce new characters or plot points by having them interrupt the fight (either the monsters leave to pursue them, or a new character arrives to chase the bad guys off).
But to be honest, I haven't seen this go very well in an RPG. It's quick and dirty, and feels like it. As a player, I'm not really in the mood for more exposition at this point because I'm too busy recovering from "losing." It usually just ends up linking the NPC/plot point to the negative feelings of the defeat.
Speculation
I suspect, but haven't had a chance to try this out, that adding difficulty to the DEM would do a great deal to help distract the players from being rescued.
Consider the standard "captured instead of killed" scenario:
DM: You're locked in the dungeon! What now?
P: I dunno. Try some stuff half-heartedly.
DM: Either that worked, or something improbably busts you out!
P: Cool. I overcome the sleeping and poorly armed guard.
DM: You're standing in a room with a cupboard.
P: Does it have all my stuff in it?
DM: ...Yes.
P: Time to move on with the campaign?
DM: ...Yes.
But what if escaping wasn't easy? What if, instead of just being a quick way of getting back on track, it was an adventure in its own right?
Say, instead, that the players wake up without their gear, at low hit points, trussed up and waiting to be slaughtered in an undead abattoir. There's a knife or two just out of reach, but it's a really hard escape artist or strength check to get at it. Give the players the opportunity to sacrifice some of their already low hitpoints for a bonus on a roll (to represent straining at the ropes), but make them decide to do it before the roll is made.
From there, it's sneaking out. Give them a series of encounters and encourage them to use stealth. Don't just let them roll out, force them to eliminate some of the patrols. Give the players a rudimentary back-stab ability if there isn't already one in the party. Make the combats attract adds if they last too long.
Finally, make the reacquisition of gear a choice. Even though they have to take it (a mid-high-level character without gear might as well pack it in in Pathfinder), the discussion will help with the illusion of choice. Put a hard encounter on top of the gear (either skill or combat, or both). Make it feel like that stuff is guarded.
From there, the players escape and continue on with their storyline. Probably picking up some ghost touch weapons on the way out.
The important thing here is for it to be difficult. Ideally you want single-instance death to be possible, while a party wipe is unlikely (you'll probably have to shift numbers around as you run the adventure).
The goal is to create something more interesting and memorable than the misbalanced encounter, with a focus on player agency and participation.
So all you have to do is write a novel, difficult-but-not-too-difficult adventure between the wipe and the next session, play-test it (because it won't conform to standard adventure guidelines), balance it, and run it. ...I think.
Good luck!
