Why did the Sahaabah use burning with fire as a punishment for some crimes?
Question

Didn’t the Prophet (blessings and peace of Allah be upon him) say: “No one punishes with fire except Allah”? Therefore isn’t burning haraam according to Islamic teachings? But in fatwa no. 38622 you stated that ‘Ali, Abu Bakr and Khaalid ibn al-Waleed burned those who committed the sin of homosexuality; were they not sinning by doing that? Even if we assume that someone is killed in a retaliatory punishment (qisaas), isn’t qisaas by burning haraam?
Praise be to Allah.It is proven in the texts that punishment by burning with fire is haraam. 
It was narrated from ‘Ikrimah that ‘Ali (may Allah be pleased with him) burned some people. News of that reached Ibn ‘Abbaas and he said: If it were me, I would not have burned them, because the Prophet (blessings and peace of Allah be upon him) said: “Do not punish with the punishment of Allah.” And I would have executed them as the Prophet (blessings and peace of Allah be upon him) said: “Whoever changes his religion, then execute him.” Narrated by al-Bukhaari (3017). 
It was narrated from Abu Hurayrah (may Allah be pleased with him) that he said: The Messenger of Allah (blessings and peace of Allah be upon him) sent us on a mission and said: “If you find So and so, and So and so, then burn them with fire.” Then the Messenger of Allah (blessings and peace of Allah be upon him) said, when we were about to leave: “I had commanded you to burn So and so, and So and so. But verily no one punishes with fire except Allah. So if you find them, execute them.”
Narrated by al-Bukhaari (3016) 
Al-Haafiz Ibn Hajar (may Allah have mercy on him) said: 
With regard to the hadith concerning this topic, what appears to be the case is that the prohibition in it indicates that this act is haraam. 
End quote from Fath al-Baari (6/150). 
This prohibition on punishing anyone by burning with fire is general in application, but the majority of scholars made an exception in the case of burning with fire by way of retaliatory punishment (qisaas) and making the punishment fit the crime. If someone burns another person then it is permissible, according to this view, to punish him by burning him, by way of retaliatory punishment. 
They quoted as evidence for that the verses in which Allah, may He be exalted, says (interpretation of the meaning):
“Then whoever transgresses the prohibition against you, you transgress likewise against him. And fear Allah, and know that Allah is with Al-Muttaqoon (the pious)”
[al-Baqarah 2:194]
“And if you punish (your enemy, O you believers in the Oneness of Allah), then punish them with the like of that with which you were afflicted. But if you endure patiently, verily, it is better for As-Sabirin (the patient ones, etc.)”
[an-Nahl 16:126]. 
The basic principle says that acting upon two sound texts that have not been abrogated is better than overlooking one of them. 
For more information, please see fatwa no. 147416 
Therefore the majority of fuqaha’ think that it is permissible to burn with fire by way of retaliatory punishment. 
Ibn Mulaqqin (may Allah have mercy on him) said: 
One group of scholars said: Whoever burns is to be burnt. This is also the view of Maalik, the scholars of Madinah, ash-Shaafa‘i and his companions, Ahmad and Ishaaq. 
End quote from at-Tawdeeh li Sharh al-Jaami‘ as-Saheeh (18/61) 
Secondly: 
With regard to what is mentioned in fatwa no. 38622 about ‘Ali, Abu Bakr and Khaalid ibn al-Waleed burning those who committed the crime of homosexuality, it may be said in response to that: 
The Sahaabah (may Allah be pleased with them), especially the most prominent figures among them, such as the four Rightly-Guided Caliphs and others, have been commended by Allah in the Qu’ran and their virtues have been proven in the Sunnah. All of that is because of their assiduous compliance and obedience to the commands of Islam, their steadfastness in adhering to them, and their efforts to call people to the faith, until they met Allah, may He be exalted, when they were like that. 
In the case of those who are of such high standing, if we come across a verdict or fatwa of theirs that appears to contradict an Islamic text, then in this case we must follow the steps outlined below: 
Firstly: we should establish the soundness or otherwise of what is attributed to them. It is not permissible to attribute anything to a person unless we are certain that it is soundly proven. 
The incidents of killing with fire that are attributed to the Sahaabah (may Allah be pleased with them) are not all soundly narrated. With regard to what is mentioned in fatwa no. 38622, to which you referred, this fatwa was to explain the views of the scholars concerning the punishment of one who commits the immoral act of homosexuality, in which we quoted all the views concerning the method of punishment for this immoral act. 
Burning was mentioned, quoting those who said that it was proven in reports from the Sahaabah (may Allah be pleased with them), such as Ibn al-Qayyim, who stated definitively that this incident was proven, as was quoted from him in the fatwa. 
But there are those who disagreed with Ibn al-Qayyim and regarded the report of this story as da‘eef (weak), such as al-Bayhaqi (may Allah have mercy on him), who said in as-Sunan al-Kubra (17/219): This is mursal. End quote. 
It is well known that mursal is one of the types of da‘eef hadiths. 
Al-Haafiz Ibn Hajar (may Allah have mercy on him) said: 
With regard to burning, Ibn Abi’d-Dunya narrated via al-Bayhaqi and via Ibn al-Munkadir that Khaalid ibn al-Waleed wrote to Abu Bakr, telling him that he had found a man among one of the Arab tribes with whom men would have intercourse as with a woman. Abu Bakr called the Sahaabah together and asked them about that, and the one who had the strictest view was ‘Ali, who said: We think that we should burn him with fire, and the Sahaabah agreed on that. 
I say: This is da‘eef jiddan (very weak). If it were saheeh, it would constitute definitive proof. 
End quote from ad-Diraayah fi Takhreej Ahaadeeth al-Hidaayah (2/103) 
Shaykh Bakr Abu Zayd commented on this report as follows: 
The verdict of the leading scholars is that it is a mursal hadith, as was stated clearly by al-Bayhaqi and ash-Shawkaani. 
End quote from al-Hudood wa’t-Ta‘zeeraat ‘inda Ibn al-Qayyim (p. 175) 
To sum up, this incident is not soundly or definitively proven. 
Secondly: in cases where a fatwa or verdict is soundly attributed, as in the story of ‘Ali (may Allah be pleased with him): 
It was narrated from ‘Ikrimah that ‘Ali (may Allah be pleased with him) burned some people. News of that reached Ibn ‘Abbaas and he said: If it were me, I would not have burned them, because the Prophet (blessings and peace of Allah be upon him) said: “Do not punish with the punishment of Allah.” And I would have executed them as the Prophet (blessings and peace of Allah be upon him) said: “Whoever changes his religion, then execute him.” Narrated by al-Bukhaari (3017). 
In an incident such as this, there must have been a reason that made ‘Ali (may Allah be pleased with him) issue the verdict of burning. There may have been the following reasons: 
1. Perhaps the hadith prohibiting burning did not reach him. The Sahaabah (may Allah be pleased with them) were just like any other people: one of them may have missed out on some knowledge, according to his situation, as Abu Bakr and ‘Umar missed out on some issues of knowledge that others had learned, even though they were superior to ‘Ali (may Allah be pleased with them all), and others also missed out on some issues of knowledge and hadiths of the Prophet (blessings and peace of Allah be upon him), as is well known.
Al-Haazimi (may Allah have mercy on him) said: 
It was narrated from ‘Ikrimah that ‘Ali burned some people who had apostatised from Islam. News of that reached Ibn ‘Abbaas and he said: I would not have burned them with fire, for the Messenger of Allah (blessings and peace of Allah be upon him) said: “Do not punish with the punishment of Allah.” And I would have executed them as the Prophet (blessings and peace of Allah be upon him) said: “Whoever changes his religion, then execute him.”. 
He said: News of that reached ‘Ali and he said: Woe to Ibn ‘Abbaas!
This hadith is proven and saheeh. 
They said: The fact that ‘Ali was surprised by the words of Ibn ‘Abbaas indicates that news of this abrogation had not reached him; when it did reach him, he adopted that view. Were it not for that, he would have objected to what Ibn ‘Abbaas said. 
End quote from al-I‘tibaar fi’n-Naaskih wa’l-Mansookh min al-Athaar (p. 194) 
2. Perhaps he had forgotten the hadith that prohibited it, and did not remember it, and the one who forgets is excused and is not sinning.
There are similar cases in the biographies of the Sahaabah in which one of them forgot a hadith and others reminded him. 
Muhammad ibn ‘Ali ibn Adam al-Ethiopi said: 
It may be that he said it – i.e., when ‘Ali said “Woe to Ibn ‘Abbaas!” – by way of approving of what he said, and that Ibn ‘Abbaas remembered what ‘Ali had forgotten. 
End quote from Dhakheerat al-‘Uqba fi Sharh al-Mujtaba (31/385). 
3. Perhaps he understood the prohibition as meaning that it was merely disliked, not prohibited, as was the view favoured by some of the scholars.
Az-Zarqaani (may Allah have mercy on him) said: 
‘Ali (may Allah be pleased with him) said: “Woe to Ibn ‘Abbaas!” It may be that he did not agree with his objection, and thought that the prohibition meant that it was makrooh (disliked), because ‘Ali thought that burning was permissible, as did Khaalid ibn al-Waleed and others, adopting a stern stance towards the disbelievers, and by way of inflicting a severe punishment on them. 
End quote from Sharh al-Muwatta’ (3/193-194) 
It is on the basis of reasons such as these that we may interpret the report that Abu Bakr (may Allah be pleased with him) burned those who committed the immoral act of homosexuality, if the report is proven to be sound. 
Shaykh al-Islam Ibn Taymiyah (may Allah have mercy on him) said:
It should be noted that not one of the leading scholars – who are widely accepted among the ummah – deliberately went against the Messenger of Allah (blessings and peace of Allah be upon him) in his Sunnah in any matter, minor or major. 
They are unanimously and definitely agreed that it is obligatory to follow the Messenger (blessings and peace of Allah be upon him), and that the opinion of anyone may be accepted or rejected, except the Messenger of Allah (blessings and peace of Allah be upon him). 
But if one of them holds a view, and there is a saheeh hadith to the contrary, then he must have an excuse for not following the hadith. All excuses fall into three categories: 
1. That he did not believe that the Prophet (blessings and peace of Allah be upon him) said that.
2. That he did not believe that he was referring to that issue when he said it.
3. That he believed that that ruling had been abrogated.
These three categories are main categories and there may be sub-categories. 
End quote from Raf‘ al-Malaam ‘an al-A’immah al-A‘laam (p. 8-9)
To sum up: what may be stated definitively is that the Sahaabah (may Allah be pleased with them) did not deliberately go against the prohibition on punishment by burning. What has been narrated from some of them (concerning that) is either not saheeh (sound), or it is saheeh but they are excused for what they did on the basis of ijtihaad, because they were qualified to engage therein. 
If the mujtahid strives his utmost to issue a correct verdict and fatwa but makes a mistake, he is rewarded and is not regarded as having sinned. 
It was narrated from ‘Amr ibn al-‘Aas, that he heard the Messenger of Allah (blessings and peace of Allah be upon him) say: “If a judge passes a judgement having striven to reach a decision, and he gets it right, he will have two rewards. If he passes a judgement having striven to reach a decision and he gets it wrong, he will have one reward.” 
Narrated by al-Bukhaari (7352) and Muslim (1716). 
For more information, please see Sharh al-Kawkab al-Muneer (4/491-492) 
And Allah knows best.