Narrated Al-Bara (radiallaahu `anhu):
The Prophet (sallallaahu `alayhi wasallam) assumed Ihram for Umra in the month of Dhul-Qa’da but the (pagan) people of Mecca refused to admit him into Mecca till he agreed on the condition that he would not bring into Mecca any arms but sheathed.
Prophet (sallallaahu `alayhi wasallam) agreed to the condition put forward by the pagans in order to be able to do `Umrah. It makes sense that he did that since the Quraysh were the custodians of Ka`bah at that time, so they had the authority.
Nowadays, the Saudi government is responsible for the pilgrims, so if they put forward any terms and conditions for those who intend to perform Hajj/`Umrah, the latter should comply. :)
Volume 3, Book 28, Number 41:
Narrated ‘Abdur-Rahman bin Abu Layla:
Ka’b bin ‘Ujra (radiallaahu `anhu) said that Allah’s Apostle (sallallaahu `alayhi wasallam) said to him (Ka’b), “Perhaps your lice have troubled you?” Ka’b replied, “Yes! O Allah’s Apostle (sallallaahu `alayhi wasallam).” Allah’s Apostle (sallallaahu `alayhi wasallam) said, “Have your head shaved and then either fast three days or feed six poor persons or slaughter one sheep as a sacrifice.”
Volume 3, Book 28, Number 42:
Narrated Ka’b bin ‘Ujra (radiallaahu `anhu):
Allah’s Apostle (sallallaahu `alayhi wasallam) stood beside me at Al-Hudaibiya and the lice were falling from my head in great number. He asked me, “Have your lice troubled you?” I replied in the affirmative. He ordered me to get my head shaved. Ka’b (radiallaahu `anhu) added, “This Holy Verse:–‘And if any of you is ill, or has ailment in his scalp (2.196), etc. was revealed regarding me. “The Prophet (sallallaahu `alayhi wasallam) then ordered me either to fast three days, or to feed six poor persons with one Faraq (three Sas) (of dates), or to slaughter a sheep, etc (sacrifice) whatever was available.
Volume 3, Book 28, Number 43:
Narrated ‘Abdullah bin Ma’qal:
I sat with Ka’b bin ‘Ujra (radiallaahu `anhu) and asked him about the Fidya. He replied, “This revelation was revealed concerning my case especially, but it is also for you in general. I was carried to Allah’s Apostle (sallallaahu `alayhi wasallam) and the lice were falling in great number on my face. The Prophet (sallallaahu `alayhi wasallam) said, “I have never thought that your ailment (or struggle) has reached to such an extent as I see. Can you afford a sheep?” I replied in the negative. He then said, “Fast for three days, or feed six poor persons each with half a Sa of food.” (1 Sa = 3 Kilograms approx.)
Volume 3, Book 28, Number 44:
Narrated Abdur-Rahman bin Abu Layla:
(Reporting the speech of Ka’b bin Ujra (radiallaahu `anhu)) Allah’s Apostle (sallallaahu `alayhi wasallam) saw him (i.e. Ka’b) while the lice were falling on his face. He asked (him), “Have your lice troubled you?” He replied in the affirmative. So, he ordered him to get his head shaved while he was at Al-Hudaibiya. At that time they were not permitted to finish their Ihram, and were still hoping to enter Mecca. So, Allah revealed the verses of Al-Fidya. Allah’s Apostle (sallallaahu `alayhi wasallam) ordered him to feed six poor persons with one Faraq of food or to slaughter one sheep (as a sacrifice) or to fast for three days.
Here’s the full ayah that was revealed in Ka`b (radiallaahu `anhu)’s case:
﴿وَأَتِمُّواْ الْحَجَّ وَالْعُمْرَةَ لِلَّهِ فَإِنْ أُحْصِرْتُمْ فَمَا اسْتَيْسَرَ مِنَ الْهَدْىِ وَلاَ تَحْلِقُواْ رُءُوسَكُمْ حَتَّى يَبْلُغَ الْهَدْىُ مَحِلَّهُ فَمَن كَانَ مِنكُم مَّرِيضًا أَوْ بِهِ أَذًى مِّن رَّأْسِهِ فَفِدْيَةٌ مِّن صِيَامٍ أَوْ صَدَقَةٍ أَوْ نُسُكٍ فَإِذَآ أَمِنتُمْ فَمَن تَمَتَّعَ بِالْعُمْرَةِ إِلَى الْحَجِّ فَمَا اسْتَيْسَرَ مِنَ الْهَدْىِ فَمَن لَّمْ يَجِدْ فَصِيَامُ ثَلَـثَةِ أَيَّامٍ فِي الْحَجِّ وَسَبْعَةٍ إِذَا رَجَعْتُمْ تِلْكَ عَشَرَةٌ كَامِلَةٌ ذَلِكَ لِمَن لَّمْ يَكُنْ أَهْلُهُ حَاضِرِى الْمَسْجِدِ الْحَرَامِ وَاتَّقُواْ اللَّهَ وَاعْلَمُواْ أَنَّ اللَّهَ شَدِيدُ الْعِقَابِ ﴾
(196. And complete Hajj and `Umrah for Allah. But if you are prevented, then sacrifice a Hady that you can afford, and do not shave your heads until the Hady reaches the place of sacrifice. And whosoever of you is ill or has an ailment on his scalp (necessitating shaving), he must pay a Fidyah (ransom) of either fasting or giving Sadaqah or a sacrifice. Then if you are in safety and whosoever performs the `Umrah (in the months of Hajj), before (performing) the Hajj, he must slaughter a Hady such as he can afford, but if he cannot (afford it), he should fast for three days during Hajj and seven days after his return, making ten days in all. This is for him whose family is not present at Al-Masjid Al-Haram (i.e., non-resident of Makkah). And fear Allah much and know that Allah is severe in punishment.)
He was asked to give fidyah (ransom) because he had to do something that wasn’t allowed in Ihraam i.e. shave his hair.
Ayyub (one of the narrators of the Hadith) commented, “I do not know which alternative was stated first.” The wording of the Qur’an begins with the easiest then the more difficult options: “Pay a Fidyah of fasting (three days), feeding (six poor persons) or sacrificing (an animal).” Meanwhile, the Prophet advised Ka`b with the more rewarding option first, that is, sacrificing a sheep, then feeding six poor persons, then fasting three days. Each Text is suitable in its place and context, all the thanks and praises are due to Allah.