Why do we use 'did' with questions using the simple past tense?

First note: In Modern English questions are formed by inverting the subject and the first auxiliary verb (the operator) to create question syntax: You have been looking for a job--> Have you been looking for a job?

The role of 'do': If no auxiliary verb is apparent, we add an operator--the verb 'do'--and inflect it for number/tense as appropriate. It is then inverted with the subject: You found a job--> Did you find a job? He reads the help wanted ads--> Does he read the help wanted ads? Notice that the main verbs here ('find' and 'read') are not in the present tense as you imagined, but are simply base forms of the verb. The tense is carried by your operator, the auxiliary verb appearing as do/does/did.

The construction you describe in which the do auxiliary is used, among other things, to form questions is called do periphrasis, and the usage of the do auxiliary in this way is termed periphrastic. Also note that it is not restricted to simple past: compare your example "Where did you go last night?" (past) with "what do you mean?" (present).

Many linguists ⁴ have been studying the origin of this phenomenon because it sets English aside in the Germanic family of languages. And whilst many different explanations have been offered during the past 50 years, the one which is currently gaining acceptance is that of a Celtic influence (more specifically Cornish).

A recent convert to the so called "Celtic Hypothesis (CH)" is no less than John McWhorter of "Our Magnificent Bastard Tongue" fame who in a recent (2008) paper revisits his previous (2002) explanation of a Viking influence and debunks a number of objections upheld by the CH opponents (recommended reading accessible to non specialists).

In fact, this construction is completely absent of Old English which closely follows the Germanic syntax¹.

Regarding the Celtic influence, let me quote McWhorter:

one would be hard pressed to name a language one had learned or was even aware of that used do in this particular way. That is, unless one is a speaker of, or familiar with, a Celtic language, in which case one is confronted with a close parallel.

The late Alvar Ellegård, a Swedish professor of English at the university of Gothenburg has plotted this graph of the appearance of the periphrastic do in Modern English².

My understanding of the chain of events is as follows.

• Following the influx of Vikings in the Danelaw, Old English looses its complex inflections system inherited from its Proto Germanic origins. There is plenty of evidence for this.
• In the process, English evolves from a synthetic language to an analytic language³.
• There is therefore plenty of room for the pervasion of some brittonicisms (among which do-periphrasis) into Middle English, which had till then been barred from entering English.

Also have a look at the famous Middle English creolisation hypothesis.

Note 3
Roughly speaking, a synthetic language relies on inflections to avoid ambiguity whereas an analytic language relies on word order to avoid ambiguities.

Note 4
Dal (1952), G.Visser (1955), Preusler (1956), Poussa (1990), Klemola (1996, 2000), Tristram (1999), Filppula (2003), Hickey (1995), Vennemann (2000, 2001), Van der Auwera & Genee (2002), White (2002), Poppe (2003). The contributions of Hamp (1975) and even J.R.R. Tolkein (1963) have also been useful.

It's not known for certain how so-called "do-support" construction arose and, in being used under all the circumstances that it is in English, it may even be a phenomenon unique to English (though there are other languages that have the equivalent structure in some of its uses).

But from what I've read, the best theories at present are essentially that a combination of other syntactic changes together led to do-support eventually arising as it is today. These include:

• arising of modal verbs as they are today (inflectionally poor, highly abstract uses beyond their "root" meanings)-- in other words, the 'category' to which "do" belongs actually arising in the first place;
• profound changes in English word order (including its move away from verb-in-second-place as in modern German) and at a more technical level possibly the arisal of something called "affix hopping" (to cut a long story short, one of the factors behind why English says "Peter often goes" with the adverb between subject and verb vs languages like French where "*Pierre souvent y va" is ungrammatical)
• the arisal of "not" after the verb as a negative marker

What also appears to have happened, at least from some data, is that do-support started life in some very specific contexts and then "spread" to others (e.g. starting in negative questions, then spreading to negative declaratives, then spreading to yes/no questions in general, ...). So what may have happened is that the combination of syntactic changes such as those above together caused a heavy motivation for *do-*support in one particular instance with the grammar of the language the way it was at that particular time, and then the construction "spread by analogy" if you like. (Or put another way, the gradual spread each time accompanied less "major" changes in the syntax.)

I'm not a specialist in historical syntax and I'm summarising what I've read (again, often in summary) from researchers such as Anthony Kroch, Peter Culiver, Alvar Ellegard. So if you're interested in more gory detail, then it's worth Googling these authors and the term "do-support" in general.