Deontic “must”, “have to” and “had to”

Solution 1:

(1) How and when did have to express the sense of obligation? What void did it fill?

Have to is an example of what's called a Periphrastic Modal (periphrastic is a technical term for 'paraphrased', meaning taking more than one word). Most English modal auxiliary verbs have at least one matching periphrastic modal construction, viz:

• must ~ have to
• should ~ ought to
• can ~ (be) able to
• may ~ (be) possible
• will ~ (be) going to
• will ~ (be) willing to

These constructions are common and have been around a long time. They arose because, as mentioned in another answer, English modal auxiliaries are defective verbs and therefore can't be used in many places where they could make sense because their morphology forbids it.

Thus, while it's possible to speak of a past obligation, you can't use must in the past to do so

• *He musted go to the dentist yesterday.

but rather a periphrastic modal that does have a past tense

• He had to go to the dentist yesterday.

Similarly for infinitives and participles

• *I would hate to must rewrite my paper.
• I would hate to have to rewrite my paper.
• *He's musting rewrite his paper
• He's having to rewrite his paper
• *He has musted rewrite his paper
• He has had to rewrite his paper

And similarly for the other periphrastic modals (examples left as an exercise).

(2) If deductions (epistemic) in the past can be expressed with must + have + PP what happened to deontic must in the past? Is there an etymological explanation?

Oh, yes. It turns out that must is itself based on an old preterite form, and there simply is no present form, which would likely be something like *muss if it existed in English.

German still has inflected modals, and the 3s present tense form of the modal verb müssen is er muss 'he must', while the past tense form is er musste 'he had to'. The final -t in German is the past tense suffix, and the final -t in English must used to be a past tense morpheme, but now it's just part of the word.

(3) What happened to the distinction between internal (subjective) and external (objective) obligation when we speak about the past? Did it ever exist?

Nothing happened to it. It's a zombie rule. Some people believe that it is real and that they always mean things that way, whatever they may actually say. But in fact it is not anything like general, as you note, and it doesn't seem to describe many uses of must and have to, let alone other modal-paraphrase pairs.

Executive Summary: Don't believe everything you read. Especially not about English grammar.

Solution 2:

"Must" is what's known as a "defective" verb, or one that list lacking particular conjugations. "Must" is the only form of the verb; it doesn't change for third versus first person, and it has no past tense form. And in fact, "must" doesn't really make sense in the past tense. Note that in the deductive sense, "must" is still in the present tense, even though it is speaking of past events. In "We must have been late, there was no one in the foyer", us having been late occurred in the past, but this having to be true is occurring in the present: it is presently true that us having been late occurred.