I cannot find an answer to the beginning use of a mikvah following Moshe at Sinai. After the Oral Torah was given to Moshe and the Jews wondered in the desert for 40 years, did Moshe and the people create traditional rain water filled mikvah baths for ritual purification, following menstruation, touching the dead, ejaculation, etc? Thanks for your understanding.
ב"ה Shalom Though you question is so obvious , it is quite challenging and it is something which needs explaining. The Torah commands us to immerse in water many times for various forms of spiritual impurities, it therefore means that the possibility to immerse in water had to be possible. Indeed the Rambam=Maimonides, (רמב"ם הלכות איסורי ביאה פרק יג הלכה ב – ג) writes that immersion took place in the desert before the giving of the Torah , since the Torah commanded the Jewish people (Shemot 19:1) to sanctify and purify themselves before the giving of the Torah. (This is also the opinion of the Semag(לאווין קטז ) However, neither say where and how the immersion took place. Furthermore, the Rambam(הלכות מקוואת א:ב) wrote that "Every place that the Torah speaks of washing of flesh and laundering of clothing [to purify] from the impurities—nothing other than immersion of the entire body in a mikveh [is meant]." This means that immersion had to be possible. So, the question remains.Where? On the one hand, there is a Midrash (תנחומא מצורע ט) that says the women did not have menstruation while in the desert, so neither did they require immersion. This was due to the fact that the Divine presence hovered over them and they lived a miraculous life. However, this does not answer the other impurities which you enumerated, neither does it answer how the Cohanim= priests were able to purify themselves. This has led many Rabbis based on the Talmud Shabbat 35 a, to explain that while in the desert they immersed themselves in the Well of Miriam which accompanied them for the duration of their stay in in the desert until Miriam's death. All the best