Since the mitzvah of tefillin is observed every day except for Shabbos and festivals, there should have been continuous knowledge as to the correct order of the parshas. So how did it come about that we now have two opinions on this matter, known as Rashi and Rabbeinu Tam?
The Ben Ish Chai (Shana alef parshas vayeira 21) brings the Levush who writes that by the kever of Yicheskal HaNavi something fell and revealed a very old pair of teffilin and it was keseder Rashi .At first we thought that it is like every machlokes that one shittah iis batel to the other one.That was until the Arizal came and said bkabbalah from the mouth of Eliyahu HaNavi zachar Latov that both shittahs are true and one should do both and from the time of Moshe Rabbeinu until the Geonim they wore both pairs.This is what the gemara in eirvuin 95b is to have two pairs ,is the place of teffilin.
The sefer Tal Oros gives a wonderful answer to this question. The complete piece, which I recommend reading to fully understand his answer, can be found here, but I will quote the most essential paragraphs:
The mitzvah of tefillin requires them to be worn the whole day. However, probably at a time later than that of the Amoraim, that is, during the period of the Rabban Savorai and the Gaonim, due to the difficult yoke of their exile, their increased dispersion and increased suffering, they became physically very weak, and so the concern of having an unclean body with regard to the wearing of tefillin became a regular concern, and from then on they were not able to wear tefillin all day.
However, in order not to abandon the tradition of wearing tefillin all day they made for themselves two pairs of tefillin. One pair was made according to the laws and holiness of tefillin which they wore once per day, during the morning prayers, and another they made as an amulet which were made and ordered not in accordance with halachah, and thus were not sanctified with the holiness of tefillin. These tefillin they wore all day as an amulet like the custom of the time of the gemara to make an amulet in the form of tefillin. The main difference between these two pairs of tefillin was that those which they wore for the mitzvah of tefillin they ordered the four parshas in accordance with the laws of tefillin, whereas those which they wore as an amulet they ordered the parshas not in accordance with these laws, and thus they did not have the holiness of tefillin and were merely an amulet.
Therefore, when subsequently there came along a period of one or two generations during which, due to the decrees of apostasy, they were not able to wear tefillin at all, after the decrees were abolished they found that the tefillin of their forefathers consisted of two types: one type had their parshas ordered like the opinion of Rashi, and another had their parshas ordered like the opinion of Rabbeinu Tam. And they forgot which were the real tefillin and which were amulets.
From this came about the dispute of the early authorities, with Rashi holding that those that were ordered according to his opinion were the genuine tefillin and the others were amulets, and Rabbeinu Tam holding the opposite. And each one supported his opinion with logical proofs, proving that only those which were ordered according to their opinion had been worn for the mitzvah of tefillin. This was the basis upon which the early authorites founded their differing opinions, and each one thought that the truth was on his side.
Rabbi Menachem Mendel Kasher suggests that at the biblical level, any order is kosher; at some later point there was a formal enactment of a "right" order, which led to this dispute.
Another answer is that in those days they didn't all wear Tefillin. This can be seen from a few places. Tosafos explains that קרקפתא דלא מנח תפילין means either someone who never put it on or someone who purposely has something against it.
Another fact to keep in mind is that Rabbeinu Tam didn't claim to invent this Shita. It is actually first brought in the name of Rav Hai Gaon.
We find by Shofar that there was more than one way how to blow before it was consolidated into one coherent, uniform practice. There is every reason to think that many types of Tefillin were floating around until Rashi decided between them, followed by his grandson.
Interestingly, the שאלת ותשובות מן השמים says that Eilu Va'Eilu Divrei Elokim Chayim, and just as there is a Mochlokes down here there is a Machlokes up there.