Does using Normal Order Evaluation instead of Normal Order Reduction lose the Normalization theorem?
NOE reduction strategy (as you define it) won't find the $\beta$-normal form of a term. For example, the normal form of $\lambda x.((\lambda y.y)x)$ is $\lambda x.x$
but NOE won't find it, because it won't reduce the inner redex $(\lambda y.y)x$ which is under the outer $\lambda$-abstraction. So it's not a normalizing reduction strategy.

However, in a typed functional language with data types like Int, if you know that some expression is of such a type, you know that it cannot be a function, so it's enough to restrict reductions to so-called Weak Head Normal Form (which is close to NOE), and it simplifies many things. See also:


http://www.haskell.org/haskellwiki/Weak_head_normal_form
https://en.wikibooks.org/wiki/Haskell/Graph_reduction#Weak_Head_Normal_Form
https://stackoverflow.com/questions/6872898/haskell-what-is-weak-head-normal-form