You have to heed the difference between two meanings of "frozen" here. In the kitchen, we frequently use "frozen" in sense 1), cooled to less than 0 Celsius, so that the water in the food (most food contains water) freezes to ice. Sense 2) is roughly consistent with what physicists describe as a phase change: a compound which has changed from its liquid to its solid phase. In this sense, alcohol freezes at -114 C, sunflower oil freezes at -17 C and coconut oil freezes at +24 C. A cook is more likely to say "solidify" instead of "freeze" in this case, but it does look and feel like freezing, so sometimes people use that word too, or can even think that if it happened, it automatically also implies freezing in the first sense.
I highly doubt that your mayo froze in the first sense. But as you see from my examples in the second sense, two things can have the same behavior at different temperatures, for example coconut oil at 24 C behaves the same way that sunflower oil behaves at -17 C. It is plausible that you created an emulsified mixture that, at the temperature of your fridge (which is probably in the +0.5 to +10 C range depending on your local food safety rules and propensity to follow them) superficially behaves similarly to how cream based air-whipped emulsions behave at -6 C to produce ice cream. That is, you got the same texture as you had frozen whipped cream, no matter the temperature of your fridge.
It is also normal for emulsions to break after freezing and thawing. So that would explain the separation you saw after taking it out again.
I cannot say exactly what single part of your recipe "caused" it, and I wouldn't be surprised if it was an interaction of many factors at once. To prevent it, you could try variations like using a mixing device which adds less air to the mixture, or reducing the speed if available, using no egg whites, using less acid, using no olive oil, and using a different temperature during whipping. It will be a matter of trial and error to find which one measure (or combination of them) is sufficient for you to prevent the problem. And of course, they all come with their own consequences, so if you discover more than one way to prevent the solidifying-separation cycle, you have to make your own choice which one to use.