I think the inherent problem with flying is the fact that you really can't legitimately box-in in the player, and therefore the player could skip over-world puzzles by simply flying above them. I also don't think flying into arbitrary boundaries to stop this problem would have made anyone any happier.
When I first saw SS, I thought it would be more like Wind Waker with a bunch of floating islands that you fly to. I wasn't happy about it really because it seemed to sub a ship for a bird.
And honestly, there is no good way to solve the problem. Zelda needs boundaries. It's the core factor in making a Zelda game. However, adventure is also a core factor. So it's difficult to find a balance.
Unlike something like Xenoblade where it's (mostly) your inexperience that boxes you in, Zelda is all about dungeons and items. So having vistas and herds of animals, waterfalls and mountains will always feel empty after a while because you can never simply push on in a direction and find your way. There will always be a need to turn around that nags you (sometimes literally), to put you on the set path to ultimately make it to the dungeon.
Now if Zelda can go back to it's original self where you're able to beat any dungeon in any order, then you could actually have the huge Xenoblade vistas. But the story would be lacking (which is actually fine by me).