"All is not lost" is simply logically incorrect to convey what is meant, and "Not all is lost" is the correct way to express that meaning:
It is clear, to use a more specific example mentioned above, that "All windows are not closed" really means "All windows are open." A person from the U.S. would however almost always say this earlier phrase when he or she is instead trying to indicate that someone has failed to close one or more of the windows; that is, has left 'only some' open. And, as long as he or she is talking to USians, would be correctly understood, despite the mild illogic. Better to say "Not all windows are closed".
I'd be prepared to bet that if by some miracle, parents suddenly all began to teach their young children the logically correct way to combine negations with quantifiers, then 15 years later, the difficulties students have to understand theoretical calculus would disappear!