Stealth is one of those few things that we are definitely interested in implementing, but we have no idea how we're going to handle it, yet. I agree with everything you said about other games, and how it's either really awesome or unpleasantly half-baked.
Some of the later Zelda games do get a little more interesting with their stealth components (the guards in OOT, the phantoms in phantom hourglass and spirit tracks), but that's still pretty binary in terms of "okay, it's time for a stealth segment now! The normal game rules no longer apply!"
One of my secondary goals for this game is to experiment around and see if we can't figure out something that feels more natural and original. I have only put a very little bit of thought into that so far, though, mainly in the realm of making sure that nothing we do prevents the addition of a stealth component later on.
I can say with certainty that there's almost no chance of there being any stealth at the start of the alpha period, since there's so much else that's more fundamental that we need to get in place first. But during alpha and beta, this is something that I want to try to tackle more. A lot of the best ideas for AI War (including such mainstays as AI Progress, or even the asymetrical AI in general), were figured out during their alpha periods, so this is no great departure for me.
