Ujm,
You asked me to explain those that hold it is a safek so I explained the “not Jewish” side of the safek. But there is also the “Jewish side” of the safek. There are two other traditions for the origin of the community: (a) they are descendants of Jews that went to Egypt and then Ethiopia after the destruction of the 1st Bais Hamkidosh (and they were supplemented by further immigration during various persecutions in Egypt and Yemen); (b) they are descendants of Shevet Dan and others of the aseres hashvatim who were exiled there during Bayis Rishon. These two traditions match better with other Jewish sources that reference the existence of a Jewish community in Africa.
For example, the posuk says in Yeshayah (11:11): וְהָיָ֣ה בַּיּ֣וֹם הַה֗וּא יוֹסִ֨יף אֲדֹ’ שֵׁנִית֙ יָד֔וֹ לִקְנ֖וֹת אֶת־שְׁאָ֣ר עַמּ֑וֹ אֲשֶׁ֣ר יִשָּׁאֵר֩ מֵֽאַשּׁ֨וּר וּמִמִּצְרַ֜יִם וּמִפַּתְר֣וֹס וּמִכּ֗וּשׁ וּמֵעֵילָ֤ם וּמִשִּׁנְעָר֙ וּמֵ֣חֲמָ֔ת וּמֵֽאִיֵּ֖י הַיָּֽם. This is describing the return of Bnei Yisrael from their golus in the times of Moshiach. It lists the places that Bnei Yisrael were exiled to during, or immediately following, Bayis Rishon and includes Kush. There are various other pesukim that reference a Jewish community in Kush or Jewish going to golus to Kush. It makes sense that the Beta Israel would be their descendants.
Moreover, it isn’t clear at all that their conversions weren’t halachically valid. The Gemara says that a person can convert, accept ol malchus shamayim, without much knowledge of the details of mitzvos. The Beta Israel had mikvah and mila. So why wouldn’t their conversions be valid?