"La Disparition" is a French novel of complex intrique by George Perec, written without using the letter "E". It was published in France in 1969 and translated into English, as "The Void", by Gilbert Adair in 1995.

Thanks, Davenport Public Library! http://www.rbls.lib.il.us/dpl/FAQletterE.htm

Oooh! Even better! Gadsby by Ernest Vincent Wright appears to be a contender in the "originally written in English" category! And the full text is online... hyperlink at the bottom of this page: http://www.lhup.edu/~dsimanek/eprime.htm