The DS9 writers didn't write themselves into a corner and then kick out the wall behind them when they realized what they had done (that would be a real deus ex machina). No, they deliberately made Sisko, who had fought so hard to get to them, call on the Prophets for help, help that was granted because he had earned it.
If people think the Prophets were a deus ex machina plot device, that just means they didn't know what a "deus ex machina" really is, and didn't see the significance of Sisko's call for help.
If there were any real deus ex machina plot saviors in Trek, it's Voyager's main deflector dish, which was always able to solve problems no matter what. Now that's a god-like machine! It's also one of the primary problems I had with the series.