Well in the book, the eagles were limited by the sizable air-force of Sauron that thesistercomic mentioned. In fact, during the final battle against Mordor, the Nazgul were still flying CAP and the eagles were merely balancing the air-superiority of Sauron, not winning the day like in the movies. It was only after the mountain went up that Sauron's air-force was destroyed, removing the limitation and allowing the eagles to save S&F.
As far as your overall question about Deus Ex Machina, the were two pieces of advice that stuck with me over the years.
1) Just let your protagonist(s) do it themselves. Basically, not using DeM in the first place, as thesistercomic also mentioned.
We writers like to put our protagonists in desperate situations, with no way out, to create tension; but if there's truly no way out, then either let them lose or don't make the situation unwinnable in the first place. In the Lord of the Rings example, what's so wrong with letting Sam carry Frodo all the way out? (IMO, nothing) Even with that though, in the book, the eagles were already there, as part of the protagonists, so one could say removing their limitation (via an act of Frodo) allowed the protagonists to do it themselves anyway, but I digress.
2) If you have a villain and they're going to get theirs sans the protagonist(s) or via protagonist(s)-from-the-grave; then think time-bomb, not lightning strike.
The story behind this advice came from a creative writing class assignment. We were tasked with rewriting the ending to a story. In the first version, the villain had to hide a prize from a previous murder because the item could link the villain to the murder. With all obstacles (and protagonists) out of the way, the villain headed toward the pier to claim their prize. It was a stormy night, the prize was in the water and while using a net on the end of a metal pole, BLAM, lightning strike, villain dead, class groans.
The best rewrite (by vote) was by a student who suggested the prize be hidden in a non-assuming hole, but as the prize is initially thrown in, something dark and scaly moves. As before, the villain is off to claim their prize. They stick their hand in the hole, quick strike, villain takes a few steps, keels over.
Technically, that student didn't change the DeM aspect of the villain's comeuppance, but did a couple of things different. First, they foreshadowed it well before the act (not minutes before the act, like the stormy night) and it felt inevitable, because easily in 9 out of 10 attempts, that hole would still be occupied. Unlike the stormy night, where the villain would only have to wait a day or two and be in the clear. Second; I personally got the sense the villain was responsible for their own demise because of the earlier murder, hiding of the item and their greed; not from some heretofore unseen impatience/stupidity of trying to claim the prize, in the water, ON A STORMY-FREAKING-NIGHT, er, sorry about that, LOL.
I hope that all made sense.