It is important to understand that there is more than one way that a scriptural passage might be brought, to which your question may have already deliberately alluded. You refer to passages being brought as proof and also as providing solidity. These are not the same thing.
In the Mishna, most of the legislation lacks a stated explanation, but amongst those things that do receive a reason we have some that are given a scriptural basis and some that are simply given a basis in tradition. The latter might be learnt through observation, or might simply be part of the received tradition, dating back to Moshe on Sinai. For an example of the former, see Sukkah 3:9 where R' Akiva learns information about the recitation of Hallel through observing Rabban Gamliel and R' Yehoshua; for an example of the latter, see Peah 2:5-6.
When it comes to legislation that is given a reason, the reason is always scriptural. This is unlike the Talmud, in which reasons might be scientific (ie: based on observation, be it medical or astronomical, etc), or rooted in a popular expression. But just because the Mishna applies a scriptural source to something, that by no means implies that the information is learnt from that actual source. In some instances, the source is merely being brought in order to buttress that opinion ("to add... solidity", as you phrased it), which the Talmud refers to as an asmakhta (אסמכתא). Literally, this means "a support" - something on which the legislation can "lean".
The process of manipulating and applying a text in order to either derive halakhic information (what in English would be called exegesis) or in order to rest information upon it (eisegesis in English) is a process that the rabbis referred to as midrash. In actual fact, midrash can refer not only to the process but to the outcomes of the process as well, and it is not always clear whether those outcomes denote a proof or a support. An example of a midrash that unambiguously denotes a support would be drash in Sukkah 28a-b that derives from Leviticus 23:42 that women are not obligated in the mitzvah of dwelling in the sukkah (a halakha that we really learn out directly from the Mishna, Sukkah 2:8). For an unambiguous example of a proof text, see the drash of R' Elazar ben Matyah in Yevamot 10:3.
(If you are interested, examples of dinim that some people believed had a proof text and others believed were halakhot from Moshe on Sinai, consider the issue of the techum shabbat in Sotah 5:3, 30b and that of tosefet shevi'it in Sheviit 1:4 and Moed Qatan 4a.)
As for your primary question, which concerns the illogicality of some of those arguments that constitute proofs, be aware that the manner in which the chachamim conducted the process of midrash was anything but arbitrary. On the contrary, while their logic may not align with the manner in which you or I more naturally read a text, they employed a system no less consistent than our own, and one that they took the time to carefully delineate and expound. This is a system of middot, which in Biblical Hebrew means "measurements" but which also possesses a more metaphysical meaning in the language of the rabbis ("qualities", perhaps).
According to some texts (such as Tosefta Sanhedrin 7:5 and Yerushalmi Pesachim 6:1), the progenitor of these middot was Hillel the Elder, and they are seven in number. According to other texts (such as a baraita recorded at the beginning of Sifra), they are thirteen in number and were developed by R' Ishmael. One formulation has them being thirty-two in number and attributed to R' Eliezer ben R' Yose haGelili, which is no longer found in its original source (a baraita), but which is alluded to by later commentators.
For an English-language description of these middot and how they function, with examples, see Strack and Stemberger, An Introduction to the Talmud and Midrash (2nd ed; Fortress Press, 1996), 15-22. You may also find some useful information in the Wikipedia entry for Talmudic Hermeneutics.
