The History of Byzantium podcast decided to adopt the radical end of the ‘sceptical view’, which does not reflect the current scholarly consensus. Even the guest they brought on to speak about the subject was Tom Holland, a popular historian who is not a specialist in the field and cannot read Arabic, Syriac or other relevant languages. You need to be aware that there is now an amateur cult following for these extreme conspiracy-style theories (eg that Islam began in Transjordan instead of Mecca) that most scholars have long since dismissed. As one of the answers pointed out, Patricia Crone, who started out as a radical skeptic and practically founded that school, moved away from many of her assertions and acknowledged that there is no serious doubt that Muhammad existed or that the Quran dates from his time.
As to the evidence, we first have unanimous agreement from the 2-3 generations after Muhammad that he existed. Early Muslim history played out on a global stage starting immediately after Muhammad’s death. No one could just make him up and have everyone just play along. Muhammad is not unique in this way, though the evidence in his case is even stronger than for other figures. To say otherwise is to engage in Moon-landing-denial-level conspiracy theorizing.
I think the Islamic historical tradition is good enough evidence as it is, but some have insisted that only non-Arabic evidence counts. The most famous example of these is the Syriac Fragment on the Arab Conquests dating from 636CE
and recording the first battles between the “Romans” and the “Arabs of Muhammad”. This is around the date given by the Muslim historians for the same battles.
If you want an accessible summary of the current state of the field, you can take a look at Sean Anthony’s recent book Muhammad and the Empires of Faith. Anthony was a student of Crone so his sceptical bona fides are beyond question. Another student of Crone, Robert Hoyland, collected all non-Arabic historical materials on early Islam in Seeing Islam as Others Saw It.