You have explained that the fight was set up in such a way that the players either will win on their own or that they lose and get rescued. The latter is a Deus Ex Machina. And here lies the problem: A Deus Ex Machina is almost always unsatisfactory and extremely hard to pull off.
I suggest listening to the Overly Sarcastic Productions discussion of the trope. 15 minutes well spent. The gist is, a Deus Ex Machina breaks so many conventions of storytelling, that makes it hard to pull off in a manner that does not upset a reader, listener or participant in a story. It's just... "And now you are saved!" Even Aristotle criticizes it in a fashion that should be internalized by every GM:
It is therefore evident that the unraveling of the plot, no less than the
complication, must arise out of the plot itself, it must not be brought
about by the Deus ex Machina.1
To prevent the Deus Ex Machina to be unsatisfactory, one of the key ways is to make it part of the plot. That is easier said than done because you need to give enough foreshadowing that such a thing can or might happen but it can't be too much to make it expected to happen at a specific moment.
Let me grab an example of an event that doesn't count as a Deus Ex Machina using LotR as an example: The Arrival of Gandalph with the Riders of Rohan. Yes, it is unexpected that Gandalf leads them and that they arrive at that very moment, but the reader knows that part of the riders was not in Helm's deep, and that people were hoping for that relief strike.
On the flip side, the Eagles that carry Frodo back from the volcano, those are a real Deus Ex Machina, and they are never explained why they were not used to get him to Mordor in the first place, making them leave a very stale aftertaste.
What Deus Ex Machina works for Running RPGs?
Let's follow OSP's classification of Dei Ex Machinae and see which can work:
Negative Foreshadowing
When the DEM contradicts the plot so far, it makes the story stale and bad, they need extreme cleanup work after... let's just say: Don't Do It deep in the plot. Don't contradict your plot to solve a problem. In my years as a player and GM, it rarely worked out that players found it interesting when the whole world they thought was working in one way was wrong in a crucial aspect. That's a little too general. Or to be more precise: it can work out, but only in a very specific way.
I have seen this type of foreshadowing work really well and actually outshine other ways, when the game is all about the discovery that came with the Deus Ex Machina. Like, it turns out that there actually are Great Old Monsters (like in Call of Cthulhu), you are actually superpowered (like you play Exalted, but all characters start as humans), or the world the players play in turns out to be nothing like expected. However, on a technicality, those cases actually have Meta-Foreshadowing from the game system you play, so technically those are low foreshadowing.
No Foreshadowing
The ideal, like from the greek drama. It is not contradicting... but pulling it off is tricky. As you portrayed, you ended up here. The NPC was not shown before, but it can be justified in hindsight. You need to explain later why the whole thing happened now, but it doesn't change the fact that you struck them with DEM and it feels cheap to them.
Low Foreshadowing
This works if prepared well. Players know that something will save their bacon when the proverbial excrement hits the fan, and so they delve into it in Exalted, trying to make that moment of becoming an Exalted really exciting.
High Foreshadowing
This is like... a magic artifact that could solve a boss battle. The players in my Year of the Griffon game got their fingers on the horn to blow in the moment of utmost dire need, to call a literal godly being to a fight. They turned the prelude to that fight, which was a cutscene between a pair of otherworldly combatants, into their final stand, in which their only goal was to actually sound the horn three times in succession. Everybody knew what would happen when the third sound came, but that actually was what made it memorable for the players.
The Eagles from LotR are technically here because they are mentioned a couple of times, but they also make an example of bad execution. We don't know why they were not used to fly them in, or why they only were used on the way out.
Conclusion?
How well a DEM comes over is very dependent on the surroundings. You fell for one of the many traps of it, the players felt cheated and that the whole thing was rigged... because as nitsua60 pointed out: it was. The only thing you can do now is Damage Control. Talk to your players, figure out what went wrong, and try to better yourself. Apologize. And then, get back into the fight and try to become the best GM you can.
In my experience, a good Deus Ex Machina that makes players happy does not fully solve the problem itself. It helps in solving the problem, and at times, triggering it becomes a problem in itself! Because of this, I tend to lean on the helper Deus Ex Machina (Chekov's Gun style). Instead of having the NPC wipe the enemy, it could have just bolstered the numbers or given a little boost - or just a short distraction for the enemy, and it would have massively shifted how the scene felt.
Players rarely think they are in an actually impossible situation unless they are really deep in the hole. That makes pulling on that for a good Deus Ex Machina quite harder, making it nigh impossible to pull off a solving Deus Ex Machina without getting the player upset.
1 - Aristotle: Poetics, Part 15(B): The Unraveling of the Plot