In linguistics, word tense is marked by the first auxiliary in a verb phrase.
In this case the second sentence can be rearranged to the deep structure: "He did have to wait for how long?", in which case, the word "do" conjugated in past tense acts as the tense marker and renders conjugating "have" unnecessary.
For "George had to wait a very long time", it can be deconstructed to
"George [noun] had [auxiliary, past] (to wait) [verb phrase] ({for} a very long time) [prepositional phrase]".
vs.
"He [pronoun] did [auxiliary, past] (have to wait) [verb phrase] (for how long) [prepositional phrase]".
The arrangement of words in "How long did he have to wait for?" is called preposing, and is a very common feature of English