Deus ex machina persists despite being widely considered a flaw in plotting because it holds a strong appeal to us as writers. No matter how hopeless the protagonist's situation becomes, no matter how outclassed the protagonist is, when the cavalry comes thundering over the hill he is saved. It also guarantees that the final situation will be as you want it. Good will triumph, the hero will get the girl, the mystery will be solved, the good guys will live happily ever after and the bad guys will be punished. Any insoluble problem can be solved, any unstoppable threat stopped, any unchangeable situation changed. You're guaranteed it will happen because you decided to make it happen.

In short, it's the easy way out.

But your reader will feel cheated. The protagonist is expected to work for his success, not have it handed to him on a silver platter. Consistency is prized in a good plot; the resolution should grow out of everything that precedes it, not just appear when needed. While the ending should be unexpected or surprising - or at least not predictable - it should provoke an 'ahhh, I see', not a 'what?'

With an arbitrary ending, you also have to wonder if the story had to be told the way it was. Could things have been easier or harder for the protagonist? If he had made a few decisions differently early in the story, would that change the story and its ending at all? For the deus ex machina resolution, the answer is usually "no" and raises another question: then what was the point?

The deus ex machina literary device now takes a few forms beyond the original god character appearing in person to solve all problems. The form most similar to the original is the cavalry rescue. This can be literally the cavalry unexpectedly charging over the hill, swelling the ranks of the good guys enough that they can defeat the bad guys. It can also be any person or group with the ability to solve whatever predicament the protagonist is in appearing unexpectedly to save the day. Another form, not too different, is the introduction of an item or piece of technology (or magic, in the case of fantasy) which hadn't been seen in the story until then and can be used to solve the protagonist's problem. Still another form is a skill the protagonist or one of his companions reveals right when it's needed. Finally, there's a favourite of Shakespeare and other writers of noble fantasy, the (possibly accidental) revelation of some critical information, such as the protagonists true identity, suddenly changing the reviled pauper into a noble prince, allowing him to marry the princess and solve the rest of his outstanding sub-plots by royal decree. Any of the above forms can be used in any genre of writing.

The key characteristic of all of the above is the unexpectedness. Having the cavalry charge over the hill in the nick of time isn't a deus ex machina ending if you've shown one of the protagonist's companions travelling off to fetch them, arguing for their services, and racing to the protagonist's aid - but it is if they just appear. (Note that it may still be unexpected to the protagonist.)

Similarly, all of the above forms that deus ex machina can take can be legitimized by mentioning the person, item, or skill earlier in the story. The object that can save the day should be shown in normal use earlier. The protagonist's useful skill should be shown in normal use earlier. In all cases it may be shown without hinting that it will be useful at the climax, to preserve the element of surprise. The item, skill, or person can be introduced as part of describing the settings and characters or otherwise used to advance the plot, and can then simultaneously help with characterization and eliminate a deus ex machina ending.

Ideally, the thing that resolves the climax - be it person, skill, or thing - will be worked into the fabric of the story seamlessly. A single mention of it early in the story with no other connection to the plot is barely better than the deus ex machina itself, since the consequences still aren't worked out.