This is an interesting question. I haven't an authoritative answer, but I can sketch the historical development and make some suggestions for how it came to be.
The first thing is that not is an anomaly in English: it is a kind of modifier that follows the word it modifies. This is normal in some languages, but unusual in English, where modifiers (such as adjectives and quantifiers) usually precede.
Historical forms like
I go not
with not post-modifying go actually arose from older I ne go nought (Old English, but with modern spelling for simplicity) where nought was optionally used for emphasis, and gradually became compulsory and ne disappeared. An exactly similar process can be seen in French Je ne sais pas. ("I don't know"), where the originally empatic pas is now normally required, and in everyday speech the ne pretty well disappears. This cross-linguistic process is known as Jespersen's cycle.
So in early modern English, the anomalous I go not was the norm.
The optional use of do with a verb goes back at least to Shakespeare's day: I do go is grammatical now as it was then (though today it has a special meaning, either I go habitually, or a contrastive or emphatic sense). This meant that in the negative I do not go was available as an alternative to I go not.
For some reason this form ousted the older form except for auxiliaries: we still say I will not, I cannot etc., but for full verbs, only He does not see it is available. My own theory is that the "do" form gained ground precisely because it restores the usual modifier-modified order: I do not go can be seen as having the pre-modifer do not before the main verb go. When the contraction don't is used, this is even stronger. But I've not seen this idea discussed anywhere.
In negative questions there is a further complication. The early modern English form was
Go they not?
which appears frequently in the King James Bible.
With the rise of do support in the negative (and interrogative), it appears too in the negative interrogative:
Do not they go?
and as A E says, this was still common in 1800, as can be seen in Jane Austen and other writers.
But there was another form which also appeared, I believe from a reanalysis of They do not go as They do (not go) rather than They (do not) go: when this was inverted as a question, the simple auxiliary do was inverted with the subject, and the not go stayed together, giving Do they not go?
When do not was contracted to the single word don't, on the other hand, this reanalysis was not possible, and the compound don't was what inverted with the subject, giving Don't they go?
As I said, this is a descriptive account, not really an explanatory one. But I suspect it is the best answer available.