There are only two references with usage of the word, incomplex, cited on Stanford Encyclopedia of Philosophy. One is from William of Ockham (1287-1347) with his explanation of the differences between intuitive and abstractive cognition. The other is from Adam de Wodeham (1295–1358) on the same topic, in his Lectura Secunda (which apparently he learned from Duns Scotus (1266-1308)). So it was familiar to Medieval philosophers and theologians.
Incomplex is (or should be) familiar to at least a few philosophers. Quoting from Phases of Thought in England, by Meyrick H. Carré (c.1949, p.157), who first quoted Ockham's work in the original Latin:
Intellectus nullum propositionem potest formare nec per consequens apprehendere, nisi primo intelligat singularia, id est incomplexa.
Then proceeded to make his own use of the word:
Incomplex abstract knowledge furnishes us with immediate and necessary judgements...
Gottfried Wilhelm Leibnitz, in Human Understanding (c.1896, pages 21, 237, and 398), was very familiar with the term:
...what the logicians call an incomplex term...
Cause is that which produces a simple or incomplex idea; effect is that which is produced.
...certain logicians of the Reformation who were in some measure of the party of the Ramists, were not wrong in saying that the topics or orders of invention...serve as much for the explication or very detailed description of an incomplex theme, i.e. of a thing or idea, as for the proof of a complex theme, i.e. of a thesis, proposition, or truth.
And there are numerous independent references to the word, including the 1913 edition of The Oxford English Dictionary, vol. 5 (H-K), p. 166 (along with Roget's Thesaurus and many more dictionaries).
An Outline Of Modern Knowledge, by F. Aveling (c.1932, p.332) 
Primitive and incomplex wholes become more complex and fully structured...
Basic Writings of Saint Thomas Aquinas, vol. 2, Edited by Anton C. Pegis (c.1945, p.1054)
Under the first head there are ten points of inquiry: (1) Whether the
object of faith is the First Truth? (2) Whether the object of faith is something complex or incomplex, i.e., whether it is a thing or a proposition?
Although I found plenty of references for incomplex, some might seem too obscure and dull for most readers. So I've attempted to round up a few instances in literature:
The Mistress of the Ranch, a Novel, by Frederick Thickstun Clark (c.1897, p.16)
Sam turned his full face upon her. It was a face capable of only one expression at a time, and that of some big, incomplex emotion.
The Strangers' Banquet, by Donn Byrne (c.1919, p.180)
He was too incomplex to worry about styles for men or what suited him.
In Main Currents in Nineteenth Century Literature, by Georg Morris Cohen Brandes (c.1906, p.295), speaking of Théophile Gautier:
...when (as in "Le premier rayon de mai") he reproduces the simple, almost sensual, at any rate perfectly incomplex, feeling of happiness produced by the close vicinity of the beloved one.
The Country Parson and Albert Savaron, by Honoré de Balzac (c.1897, p.152)
Who is there with a thinking brain or a wounded heart that can pass through a forest and find the forest dumb? Before you are aware its voice is in your ears, a soothing or an awful voice, but more often soothing than awful. And if you were to examine very closely into the causes of this sensation, this solemn, incomplex, subduing, and mysterious forest-influence that comes over you, perhaps you will find its source in the sublime and subtle effect of the presence of so many creatures all obedient to their destinies, immovable in submission.
So many great writers and thinkers have produced fine literature and ideas with the term, incomplex, that it seems a pity not to easily recognize its meaning and perhaps even to keep it alive with modern usage.
- "An Incomplex Introduction to Complexity-based Cryptography."
...is an elegantly phrased, creative, and clever title. It's a mouthful, but I like it. Oh, and to answer the question specifically:
- Yes, incomplex is a legitimate word.
- Yes, anyone should feel free to use it whenever they like (in context, of course).