Hmm...to me the problem is that while plot points can often happen in any order, characterization absolutely must follow a specific trajectory. Link in the Legend of Zelda is pretty much devoid of character development (or much characterization at all) - he's exactly the same (internally) at the end as he was at the beginning. Since there is no character development tied to them, the dungeons can happen in any order whatsoever, story wise.
I think when I misremember the order of plot events in a narrative I've read, I'm usually separating plot and character development in my mind. I may not perfectly remember which battle happened when in Seven Samurai, but I remember the character arc for Kikuchiyo and know generally the order his developments went in. In the film, plot developments and character developments are given hand in hand. So while certain fights could happen in any order, the accompanying character development could not.
So for a game, we are giving the player both plot development and character development. Without completely separating plot and characterization, how can events be presented in any order and still allow for character growth?
I can see how non-linear can work for a static character, i.e. each event shows another facet of who he is. However, this character isn't changing at all. Can a non-linear game effectively show a character changing over the course of a story?
i wouldn't say link is exactly the same -- presumably after 8 dungeons he's more confident because he's overcome so much. it's true that the game doesn't *portray* that to you, but it can be inferred
also, the structure of 'overcoming N challenges, loosely connected' shouldn't be underestimated; some of the greatest stories in history use that structure. a good example is the odyssey by homer; he goes from island to island, having an adventure at each one. but the order of them doesn't really matter. another example is the trials of heracles. i wouldn't exactly say that those stories are devoid of character development either, although they don't focus on it
but yes it is true that if you are writing a non-linear story, certain structures work better than other structures. but i don't think character development in non-linear stories is impossible or something, it just requires different methods
for instance, let's say you want to have a character evolve from cowardly to courageous. you could separate that into five stages: each stage has a set of events that can happen in any order, but the character, when in a particular stage of cowardly -> courageous, can only access the events particular to their current stage; after they've done a certain number of those events (not all of them, but a number of them from that stage's pool of events) they progress to the next stage. so you might have 30 events for each stage (150 events total), but the player only has to play through at least 10 of the events of each stage
as for non-linear games not having character development, i think playing alter ego would make you believe otherwise:
http://www.playalterego.com/ -- it's a non-linear game, but has some of the best character development i've seen in a game. the game progresses through stages from baby through all the stages of life, and in each stage various events are possible (although you can't see all the events in any one playthrough). it's one of the best examples of non-linear character development that i've encountered, so i encourage you to try it out, it's a classic of good design