I like Rav Zevin's theory, already shared by Joel K in his answer.
That said, though, there is strong indication that the legal differences derive from a misunderstanding. Sotah 47b says:
משרבו תלמידי שמאי והילל שלא שימשו כל צורכן רבו מחלוקת בישראל ונעשית תורה כשתי תורות
When the students of Shamai and Hillel multiplied, so that they didn't properly serve apprenticeship their [respective] rebbe, dispute multiplied in Israel, and the Torah became like two Torahs.
The disputes are blamed on there being too many students to get close to the rebbes, and therefore something was lost in the chain of transmission. Which then led to the explosion in the number of disputes.
The Maharal (on Avos 1:12) explains that the disputes derive from the rebbes' respective jobs. Hillel was the Nasi. It was his job to lead the community. Shammai was the Av Beis Din, the head of the Sanhedrin and thus the judicial system. Hillel's job was to be sympathetic; Shammai's job was to enforce strict justice. The Maharal explains that because of that lack of apprenticeship, the students' didn't realize the difference between their mentor's value, and his job. And so Beis Hillel tended to take the empathetic approach, and Beis Shammai, the more legally rigorous one.
But only because of a misunderstanding.
In any case, this Compassion (Rachamim) vs Din (Justice) dischotomy is also found in the Zohar. And based on this, for example, the the Ari haQadosh says that while today we nearly always follow Beis Hillel, in the Messianic Era we will be capable of living up to the standards of Justice, and the law will favor Beis Shammai.