First of all fiqh is based on ijtihad. Then there are 4 known madhhabs but not 4 ways in doing things as all these madhhabs have two common sources: the Quran and the Sunnah. So in cases where there's a source the possible ways are limited to the different narrations: This would mean in general you may have 2-3 or less possible ways. If it comes to ijtihad (concluding rules from the sources for new problems) you still might find a consensus or sometimes even not find a consensus in the same madhhab. In many cases even the Founders of those madhhabs had two different opinions because they knew about different or contradictory hadiths or maybe changed their mind later based on new information or just a review of their former fatwa on a matter.
Historical intro
When the Messenger of Allah (Peace be upon him) died, there was no clear instance on what is to do and what not. The sahaba (May Allah be pleased with them) were wide spread in the Muslim countries where they have been teaching Islam and Sunna and Quran, while many died in Medina and Hijaz some have been living in 'Iraq and a-Shaam. At the time of sahaba there have been 4 major "scholars" known by the Abadillah the 4 Abdullah's : Abdullah ibn 'Omar, Abdullah ibn Masu'd, Abdullah ibn al-'Abbas and Adbullah ibn 'Amr ibn al-'Aas. Of course many other sahaba have been there too but those four have had the most influence. For example maybe a sahabi like abu Huraira knew and collected a lot of hadiths (even after the death of the Prophet) but an other had better skills to conclude rulings from them. Scholars such as ibn Hazm counted 18 sahaba who had what we may call an own madhhab or ijtihad (opinion), an-Nasa-i counted 22 of them! While among the tabi'in the amount was approximately doubled.
A division in opinions began already at the time of sahaba and they have had influence on the tabi'yn and so on. But they have had also some kind of consensus in known cases. You must understand, that at this time nobody had a good database to search for a hadith so they all could only conclude rulings from the given data or information they had as this was what they have been taught (See for example in Sunan abi Dawod, Sunan an-Nasa-i, Jami' at-Tirmidhi). For some more or less obvious reasons the sahaba who have been living in the 'Iraq had much more to deal with new Issues, so because they have been less in quantity they may also have less sources for hadith which made them with the time more and more flexible and able to conclude rulings from the "few" sources they had and build up juridic jurisprudence. While those in Hijaz haven't had that quantity of "new" problems.
So in 'Iraq a ra'y (opinion based) jurisprudence school has developed with the time, while in al-Hijaz the school was mainly based on the original sources -mainly the hadiths and sunna- (ahl al-Hadith or al-Athar).
Please also note that even at this very early days there have been some political and tribal differences, who lead to some disagreements which may find their source more in these "internal combats" rather than in the Islamic sources of knowledge: so some of the followers of those sahaba later refused ahadith narrated by "disputants"! I'm not saying that the sahaba would agree with this, as we don't know, but this is what happened afterwards!
See also this fatwa.
What is the origin of the concept of there being four ways to do things?
There's no origin of that concept there are factors:
one of them was the necessity to fix a madhhab, as due to the fact that each scholar had his own opinion, ordinary people were seeking guidance, as everybody was claiming that he was following the Qur'an and sunnah and at the time of the tabi'in there already have been about 40 mujtahid with his own opinions, which are based on these basics.
An other are political factors like the hanafi school being for a part of the Abbasid Dynasty the preferred school (Abu Yousuf the student of abu Hanifa was the highest qadhi/qazi after his master refused and has been tortured) and then after the fitnah of quran the hanbali school was much appreciated for a certain time. The maliki school was appreciated because of the knowledge of Imam Malik as his book was one of the first sahih hadith collections (It includes at least 500 hadiths which you may find in any other hadith collections beside some 200 more in the final revision and you may find in those books ahadith narrated by him which are not in the al-Muwatta'a as it was more a book of ahkam and fatwa). The student of abu Hanifa Imam Muhammad ibn al-Hassan has narrated the muwatta' and when he used to recite from it he had always a bigger audience as in his other lessons. Note that many teachers of Imam Malik where his students later, as he was one of the first whom have been given the title Amir al-mu'minyan fil hadith, his muwatt'a is a revised summary of much more then 100000 hadiths and narrations about ahkam he has collected beside some of his fatwas. Imam a-Shafi'i was welcomed in Egypt at first as he was a student of Malik, but then more and more accepted by the former students of Imam a-Laith ibn Sa'ad. But at the time there have been many other good scholars who had reached a high level of knowledge some were even set much higher than those four like Sufyan ibn 'Oyyana, Sufyan a-Thawri, Abdullah ibn al Mubarak, al-Awzaa'i , a-Laith ibn Sa'ad.... and among the tabi'yn an even larger number of great scholars whom (maybe) had a madhhab of their own and followers.
People of the Maghreb and Andalusia after converting to Islam -via Preachers and fighters from a-Shaam- adapted at first the madhhab of Imam al-Awzaa'i (from a-Shaam) and afterwards had a strong relationship to Medina as the "city of the Messenger of Allah (Peace be upon him)" so they were among the first to become shi'a or "maliki" (but also KJhwarij found refuge there far away from the strong hand of the Ummayad or 'Abbasid Caliphs or Kings) and they also -more and more- adapted the (quran) reading of imam Nafi' as a major "standard". Of course if in a major city a qadhi/qazi following one madhhab has been appointed he would be in favor for colleagues of the same madhhab! For example: it's said that Yahya ibn Yahya al-Laithi the Andalusian scholar, who was the last one to have his muwatta' version revised by Imam Malik had good relationships to the rulers in Al-Andalus therefore it was up to him to choose the qadhi's. The same applied during the 'Abasid reign for the hanafi school due to Abu Yusuf the student of abu Hanifa who was the highest qadi for a long term.
Now if you want to know at what time the sunni school limited the madhhabs to only four. then it's hard to say but maybe this happened somewhere between the 5th and late 6th century due to a consenting silent (as nobody tried to do ijtihad al mutlaq and all scholars only wrote comments on former madhhabi sources). At least Qadhi 'Iyad pretend in his book about the scholars of the Maliki school that in al-Maghrib one couldn't anymore find scholars of any other school then the maliki madhhab.
Note that ibn Hazm (a-dhahiri) lived only a century before in al Andalus and the later dynasty of the Almohads الموحدون encouraged ijtihad in any madhhab no matter if it was in fiqh or 'aqidah.
Some people say it was ibn Salah (others have also been named) that declared the closure of the doors of ijtihad and that only four madhhabs are exiting. But the dhahiri school still exists in the salafi thoughts and the books of ibn Hazm, which were brought to the orient by ibn 'Arabi.
An answer for the quoted hadith
as you may see in my answer here and read in the relevant link the answer of ibn al-Majushoun a Student of Imam Malik, who has been asked about this matter which the maliki school rejects even if there have been an athar (Hadith or only teaching of a sahabi) about it in the Muwata' with the Answer: "We have quoted it and rejected it so that people know, that we knew it and rejected it" ...why? Because they either had a better/stronger narration or something based on the osol of their madhhab.
فقيل لابن الماجشون: لمَ رويتم الحديث ثم تركتموه؟ قال: ليعلم الناس أنا على علمٍ تركناه.
Note that there are two narrations in the book that we now call al-Muwatta' (as there have been as much as there have been approved versions of the students of Malik, but maybe less then 10 have still survived until today, beside other scholars later -apparently- also adapted that name, but i don't know about an other muwatta') which speak about "placing the hands right over left in salat" and these one was one of the rare narrations which Malik accepted from an 'Iraqi narrator who has been later considered as weak. While the other is a marfu' narration. In the Maliki madhhab there's no consensus about this very matter (those who refer to the popular placement of the hands among malikis are basically referring to mukhtassar khalil, while the maliki's of al-'Iraq have always chosen the well known option), but note that even in the shafi'i sources you may find a saying of Imam a-Shafi'i where he is preferring not to place the hands right over left. Why?: Because of many reasons the hadith of the man who didn't pray well for example is suggesting that each body part should find it's place some scholars said the natural position of the hand while standing is beside the legs! Some others said that not placing them one over the other is a major challenge (as when placing them as described you may not have been challenged with your khushu') so you may gain thawab. But one point might be that only people from al-'Iraq narrated this (and in hijaz narrators from al-'Iraq where not that much trusted). An other source is that the major narrator of the right hand over left in an other hadith didn't have any objections to this ... so it is an ijtihad matter in first place! As for the example inquiry you may also read Is there Hadith for the Maliki way of praying?.
