I think the OP is not only thinking himself but also making us think to know as to which of the two actions happened first. As a good rule of thumb, I have never thought so whenever I used the word "until" as a conjunction in the past. However, I keep it in mind that the "until" is used as a conjunction in two senses as follows:
When it's used in the first sense and we are talking about events in the past, it's very common that the main clause (mc) and the subordinate clause (sc) with "until" are both in the simple past or the mc is in the past simple and the sc is in the past perfect. Such a sentence is usually positive. Please look at the following sentences:
*I waited until the doctor came/had come.
*They played until it got/had got dark.
The use of the past perfect in the above sentences in the sc is not because the events happened earlier but because we want to emphasize or accentuate the events in the mc.
The use of the past perfect in the mc to stress the event,though not incorrect, is found seldom. For example, I had waited until the doctor came.
Now we come to the sentence in question:
The people took shelter under a tree until the rain stopped/had stopped. The sentence is 0K in light of the above; there is no doubt about it.
The people had taken shelter under a tree until the rain stopped. The use of the past perfect in the mc, though not common, is grammatically correct.