Background: I know to avoid Deus Ex Machinas - meaning to me a sudden and unexpected solution arriving out of nowhere to save an otherwise unsolvable problem. They are often indicative of a writer who has written himself into a corner, and has to rely on a DXM to get him out of the pickle he's in.
There are two answers to dealing with a DXM. The first is obviously to rework the plot, and the main conflict, so that there is a way to solve it. If that's not an option, and you have to use the DXM, you have to spread clues throughout the book as to its existence, so that when it is revealed it is a great twist rather than a DXM.
I recently ran into a DXM situation in my current tale. In trying to solve the problem, I arrived at an interesting form of DXM, and was curious if it would still be considered a DXM, or if it would instead be a good twist.
The good guy and his band of faithful followers (at least what's left of them) has hit rock bottom. All options have been closed off in their attempts to get the plot device. In a hail Mary attempt, they've struck at the heart of the enemy's defenses, where he holds all fifteen of the plot devices. If they can get even just one, they'll have enough bargaining power to achieve their goals.
Unfortunately, they are captured. At this point, the bad guy could easily execute them. And this is where the DXM comes in.
Lo! The villain doesn't want to kill them. The villain has recently conquered all of the land, and executing his enemies would only inspire fear in his new subjects. He wishes to rule through peace, not fear. He therefore decides instead to pardon them, and use the fifteen plot devices to fulfill their goals.
Reasoning: Now that sounds really bad, but here's the thing: killing the good guy makes no sense whatsoever. The good guy and his companions were never much of a threat to the antagonist. He might have been forced to kill them while they were free and active, but now that they are captured and right in front of him, there's no point.
This antagonist is not an inherently bad person. He's driven and very focused on keeping all fifteen plot devices, but now that he has them, he is intent on using them to rule his new land with peace, not fear. He is no tyrant, and doesn't want to be seen as one. He knows that executing his enemies will spread fear and dissent amongst those he now rules, while pardoning them will turn him into a generous benefactor among his new subjects.
One final point is that granting the goals of the good guy and his companions also conveniently gets rid of them: they in fact desire to leave the land altogether, and the fifteen plot devices are the way home.
Question: Based on all this, it makes no sense to kill them. Because of this, is the sudden reversal of attitude on the villain's part simply a twist? Or is it still going to seem like a DXM, and perhaps turn off readers?
What this question is not: This is not a 'how to write' question, where I'm asking for alternative solutions to solving the main conflict. Similarly, I'm not asking for advice on how to work the plot so that seems like less of a DXM. This question is asking if this twist, as it is and with what I have provided (so assuming there's no other hints about it), would still be considered a DXM even after it is explained. (I'm assuming it will seem like one at first no matter what I do. It comes down to how the reader sees it once he understands how illogical the alternative [killing the good guys] is.)
Also note that this question can easily help other writers with a DXM where the alternative is illogical. I am using my own writing purely as an example.