Patur Aval Assur –
First, let’s establish what the Rambam says. He writes (?”? ????? ??”?):
???? ???? ???? ???? ?????? ???”? ????? ???? ?”? ?????? ????
Pashtus he is saying that a non-Jew’s shechita is only forbidden mid’rabbanan where the non-Jew is not an idolater.
The Kesef Mishneh understands this as a machlokes between the Rambam and Tosafos (the key Tosafos is ????? ?: ?”? ????), as he says:
??? ?????? ???? ??? ????? ???? ?”? ???? ??? ?????? ????”? ??? ??? ?”? ????? ???? ????? ????? ????? ???? ???? ?? ????? ???? ?????
To take the Rambam’s words ???? ???? ???? and turn them into a d’oraisa just does not seem accurate.
That established, let’s turn to Tosafos’s question. Tosafos asks how—even if we held like R’ Anan—Eliyahu could have eaten the meat, given that Rav holds ??? ?????? ?? ???? is forbidden because it may have come from a non Jew. Tosafos answers that this much the Gemara assumed he relied on the ?????; it was the leap that the ????? permitted the forbidden that the Gemara was at first unwilling to take.
You’re asking that according to the Rambam, why lemayseh did the Gemara have to answer that the ????? permitted the meat that would have been forbidden, instead of just answering that the ????? revealed to him that it was not shechted ??? ?”?? Here are a some suggestions:
1) Maybe according to the Rambam the Gemara meant just that. As for Tosafos’s problem, maybe the Rambam would say ??”?, the Gemara could have asked ??????, it just didn’t.
2) Even if Eliyahu was positive that the meat was not shechted ??? ????? ???, it could have still been assur mid’rabbanan for him to eat meat from an animal shechted by a non-Jew, depending on when this ??? was enacted. Eliyahu could have required the ????? to permit this issur d’rabbanan.
3) The Rambam could argue that ??? ?????? ?? ???? may not have applied in this case, either because (a) there were no butchers in the vicinity that did not follow hilchos shechita; or (b) the meat was still sealed in the original ?? ???? ????? packaging.