I don't know about "na wai e 'ole" being a modern construction. There is an 'olelo no'eau - "Na wai ho'i ka 'ole o ke akamai, he alanui i ma'a i ka hele 'ia e o'u mau makua" (Why shouldn't I know, when it is a road often traveled by my parents) which was uttered by Liholiho. I've also heard it as "na wai e 'ole (i) ke akamai ..." I would probaly translate that as "Who would disagree/argue/refute..." but Mrs. Puku'i translated it as "Why shouldn't I."
Ha! Shows what I know! Mahalo for clarifying that!