Open world can work just fine. Starshatter does some things quite well in this regard, though it's only semi-open world, and has very limited fixed campaign constraints (it is supposed to be a dynamic campaign). What happens is that the player is constrained in where he or she may go, and how much time he or she may take to complete a mission, because objectives are time-sensitive. Making this enjoyable all the time is the challenge.
Now, this certainly does result in a different game type, and the means of telling a story is achieved in different fashions than a fixed-mission type game... or perhaps that doesn't necessarily need to be true either. However, an open world has the advantage of being endlessly replayable, with no same mission, or seldom the same mission in a game. I think once you can make a stroy-driven game truly dynamic, you've got yourself a winner.