My intuition as a native speaker is that 1 is preferable to 3 and 4 is as good as 2. Number 3 uses two past tense verbs, even though the initial clause has a very clear cue that past perfect is required: the word until.
But what about number 4 versus number 2?
Two things seem to make simple past natural here. The first is the presence of before rather until. The first refers to some event at any previous time, possibly disconnected from receiving the phone call. With until, though, the event, action or state is presented as continuing until the moment of the phone call, which means that the perfect is required.
Consider:
Before I met you for lunch, I did not get a croissant from the corner bakery.
No problem here.
Until meeting you for lunch, I had not gotten a croissant from the corner bakery.
Clearly we cannot replace this with the simple past.
Until meeting you for lunch, I did not get a croissant from the corner bakery.
But when before fills the same role as until, it plays by the same rules:
Before meeting you for lunch, I had not gotten a croissant from the corner bakery.
Now that before refers to an ongoing state that continues until the present, we must use the past perfect.
We see here that most people would probably use number 4 to refer to a single event, and number 2 to refer to a past situation, that of having visited a store in the past. To convince yourself of this, switch it around, add another verb, and expand the contraction: I had visited a store and bought some food before you met me. This seems to refer to someone who is being accused of not knowing how to shop, does it not?
However, these are not hard-and-fast rules. Number 2 might still work if the consequences of the visit were viewed as continuing into the present.