I have not so far be in the position to play Death on Wing with the overlord losing the first encounter, but knowing the quest and reading about the dissatsifaction, I had been thinking of one way to make it less of a pointless exercise of set-up, one hero turn and then having to remove the parts form the board again.
The issue is that in a three or two player game, Beltir is potentially open to six (or four) attacks without the overlord being able to do much about it (with the basic overlord deck, all one can do is remove one action through stunning the heroes via pit trap and using dark fortune to reroll bad defence dices).
Thus, my suggestion would be, simply place a quest token as a bolder on the bridge so that the heroes need to go through the elemental (or possibly remove the boulder, if allowed).
That way, the quasi automatic victory for the heroes on turn 1 could be avoided and it also dodes not change anything if the overlord wins the first encounter as the heroes have to face the elemental then any way.
What would your thoughts be?