What contemporary historical records of the existence of Muhammad, the prophet of Islam, exist or are known to have existed at some point?
Yes, Muhammad existed.
In his book, Seeing Islam as Others Saw It, Robert G. Hoyland discusses numerous contemporary non-islamic sources that reference Muhammad. The details align quite well with somewhat later islamic sources, which gives them quite a bit of credibility.
Then God raised up against the sons of Ishmael, as the sand and sea shore, whose leader was Muhammad. Neither walls nor gates, armour or shield, withstood them, and they gained control over the entire land of the Persians. (Pre-Islamic Persian chronicle, 660 a.D.)
The details of his life and teachings are, however, murky.
Reference from non Islamic sources.
The 8th century Byzantine historian, Theophanes acknowledged Muhammad's (saw) existence in his "Chronicle":
The Chronicle of Theophanes: Anni Mundi 6095-6305 (A.D. 602-813) [page 34].
Sebeos, an Armenian bishop of the House of Bagratuni wrote about Muhammad in the 7th century. He wrote:
At that time a certain man from along those same sons of Ismael, whose name was Mahmet [i.e., Mụhammad], a merchant, as if by God's command appeared to them as a preacher [and] the path of truth. He taught them to recognize the God of Abraham, especially because he was learnt and informed in the history of Moses. Now because the command was from on high, at a single order they all came together in unity of religion. Abandoning their vain cults, they turned to the living God who had appeared to their father Abraham. So, Mahmet legislated for them: not to eat carrion, not to drink wine, not to speak falsely, and not to engage in fornication. He said: 'With an oath God promised this land to Abraham and his seed after him for ever. And he brought about as he promised during that time while he loved Ismael. But now you are the sons of Abraham and God is accomplishing his promise to Abraham and his seed for you. Love sincerely only the God of Abraham, and go and seize the land which God gave to your father Abraham. No one will be able to resist you in battle, because God is with you.
Birmingham Quran manuscript. In 2015, a manuscript of the Quran was discovered in the archives of the University of Birmingham. The manuscript was radiocarbon dated in 2015 between 568 and 645 with 95% accuracy. It contains parts of chapter 18-20 of the Quran. It has verses which according to wikipedia, addresses Muhammad.
Introduction, verses 1–8 chapter 20
This section is an introduction to the sura. It begins with God addressing Muhammad, then lists several of God's characteristics and praises Him. In this section, there is also a mention of the Qur'an as a reminder of God's existence, a theme that is seen throughout the Qur'an. One of the two verses in this sura mentioned in al-Wahidi's "Asbab al-Nuzul" is verse 2. According to al-Wahidi, God sent this verse to Muhammad because the Quraysh were saying that Muhammad was distressed because he left their religion, and that God only sent down the Qur'an to distress Muhammad. -- Wikipedia
The verse that addresses Muhammad says:
We have not sent down the Qur'an unto you (O Muhammad) to cause you distress, -- Quran 20:2
This manuscript dates back to the time of Muhammad, (570-632) addresses him and thereby demonstrates his existence.
Summary: There is acceptable scholarly evidence for the existence of a historical individual named Mohammed but only disputed scholarly evidence when one wants to prove that Mohammed is a "prophet".
So, did Muhammad exist? In Spencer’s view, “as a prophet of the Arabs who taught a vaguely defined monotheism, he may have existed. But beyond that, his life story is lost in the mists of legend.” Ultimately, “as the prophet of Islam, who received (or even claimed to receive) the perfect copy of the perfect eternal book from the supreme God, Muhammad almost certainly did not exist”. Source: The Revisionist Case That Muhammad Did Not Exist
Nonmuslim sources for the historical Mohammed:
"Seeing Islam as Others Saw It: A Survey and Evaluation of Christian, Jewish and Zoroastrian Writings on Early Islam" by Robert G. Hoyland contains a collection of Greek, Syrian, Coptic, Armenian, Latin, Jewish, Persian, and Chinese primary sources for eyewitness accounts of Islam. Some of the following evidence is also mentioned in that book.
1. A Record Of The Arab Conquest Of Syria, 637 CE
and in January, they took the word for their lives (did) [the sons of] Emesa [i.e., Ḥimṣ)], and many villages were ruined with killing by [the Arabs of] Muḥammad and a great number of people were killed and captives [were taken] from Galilee as far as Bēth [...] and those Arabs pitched camp beside [Damascus?] [...] and we saw everywhe[re...] and o[l]ive oil which they brought and them. And on the t[wenty six]th of May went S[ac[ella]rius]... cattle [...] [...] from the vicinity of Emesa and the Romans chased them [...] and on the tenth [of August] the Romans fled from the vicinity of Damascus [...] many [people] some 10,000. And at the turn [of the ye]ar the Romans came; and on the twentieth of August in the year n[ine hundred and forty-]seven there gathered in Gabitha [...] the Romans and great many people were ki[lled of] [the R]omans, [s]ome fifty thousand [...]. Source: List Of Dated Texts Mentioning Prophet Muḥammad From 1-100 AH / 622-719 CE
However, the condition of the text is fragmentary and scholars feel many of the readings as unclear or disputable.
2. Thomas The Presbyter (c. 640 CE / 19 AH)
AG 945, indiction VII: On Friday, 4 February, [i.e., 634 CE / Dhul Qa‘dah 12 AH] at the ninth hour, there was a battle between the Romans and the Arabs of Muḥammad [Syr. tayyāyē d-Mḥmt] in Palestine twelve miles east of Gaza. The Romans fled, leaving behind the patrician YRDN (Syr. BRYRDN), whom the Arabs killed. Some 4000 poor villagers of Palestine were killed there, Christians, Jews and Samaritans. The Arabs ravaged the whole region. Source: List Of Dated Texts Mentioning Prophet Muḥammad From 1-100 AH / 622-719 CE
3. Sebeos, Bishop Of The Bagratunis (660s CE / 40s AH)
At that time a certain man from along those same sons of Ismael, whose name was Mahmet [i.e., Muḥammad], a merchant, as if by God's command appeared to them as a preacher [and] the path of truth. He taught them to recognize the God of Abraham, especially because he was learnt and informed in the history of Moses. Now because the command was from on high, at a single order they all came together in unity of religion. Abandoning their vain cults, they turned to the living God who had appeared to their father Abraham. So, Mahmet legislated for them: not to eat carrion, not to drink wine, not to speak falsely, and not to engage in fornication. He said: 'With an oath God promised this land to Abraham and his seed after him for ever. And he brought about as he promised during that time while he loved Ismael. But now you are the sons of Abraham and God is accomplishing his promise to Abraham and his seed for you. Love sincerely only the God of Abraham, and go and seize the land which God gave to your father Abraham. No one will be able to resist you in battle, because God is with you. Source: List Of Dated Texts Mentioning Prophet Muḥammad From 1-100 AH / 622-719 CE
4. Khuzistan Chronicle or Anonymous Guidi (c. 660s CE)
Then God raised up against them the sons of Ishmael, [numerous] as the sand on the sea shore, whose leader (mdabbrānā) was Muḥammad (mḥmd). Neither walls nor gates, armour or shield, withstood them, and they gained control over the entire land of the Persians. Yazdgird sent against them countless troops, but the Arabs routed them all and even killed Rustam. Yazdgird shut himself up in the walls of Mahoze and finally escaped by flight. He reached the country of the Huzaye and Mrwnaye, where he ended his life. The Arabs gained countrol of Mahoze and all the territory. They also came to Byzantine territory, plundering and ravaging the entire region of Syria. Heraclius, the Byzantine king, sent armies against them, but the Arabs killed more than 100,000 of them. Source: List Of Dated Texts Mentioning Prophet Muḥammad From 1-100 AH / 622-719 CE
5. John bar Penkaye (687 CE / 67-68 AH)
Having let their dispute run its course, after much fighting had taken place between them, the Westerners, whom they call the sons of ’Ammāyē, gained the victory, and one of their number, a man called M‘awyā [i.e., Mu‘awiya], became king controlling the two kingdoms, of the Persians and of the Byzantines. Justice flourished in his time, and there was great peace in the regions under his control; he allowed everyone to live as they wanted. For they held, as I have said above, an ordinance, stemming from the man who was their guide (mhaddyānā), concerning the people of the Christians and concerning the monastic station. Also as a result of this man's guidance (mhaddyānūtā) they held to the worship of One God, in accordance with the customs of ancient law. At the beginnings they kept to the traditions (mašlmānūtā) of Muḥammad, who was their instructor (tā’rā), to such an extent that they inflicted the death penalty on anyone who was seen to act brazenly against his laws. Source: List Of Dated Texts Mentioning Prophet Muḥammad From 1-100 AH / 622-719 CE
6. Stephen of Alexandria (775-785)
But the violence of earlier times is not forgotten. Stephen of Alexandria (775-785) reminds his flock that “In the desert of Ethrib there had appeared a certain man from the so-called tribe of Quraysh (Korasianou), of the genealogy of Ishmael, whose name was Muhammad and who said he was a prophet. He appeared in the month of Pharmuti, which is called April by the Romans, of the 932nd year (from the beginning of Philip [~571 CE]). He has brought a new expression and a strange teaching, promising to those who accept him victories in wars, domination over enemies and delights in paradise.” which is a neat summary of the main strands of early Islam. Source: Early non-Muslim sources concerning the advent of Islam
Islamic books such as Quran was found to be difficult to use as a historical source since it is often highly obscure.
Everything else about Mohammed is more uncertain, but we can still say a fair amount with reasonable assurance. Most importantly, we can be reasonably sure that the Qur'an is a collection of utterances that he made in the belief that they had been revealed to him by God. The book may not preserve all the messages he claimed to have received, and he is not responsible for the arrangement in which we have them. They were collected after his death – how long after is controversial. But that he uttered all or most of them is difficult to doubt. Those who deny the existence of an Arabian prophet dispute it, of course, but it causes too many problems with later evidence, and indeed with the Qur'an itself, for the attempt to be persuasive. Source: What do we actually know about Mohammed?
There is also actual linguistic errors noted in the Quran which is mentioned here found by scholars Burton and Dashti and a German scholar Gerard R Puin challenges the conventional understanding of the Koran with the following statement.
My idea is that the Koran is a kind of cocktail of texts that were not all understood even at the time of Muhammad. Many of them may even be a hundred years older than Islam itself. Even within the Islamic traditions there is a huge body of contradictory information, including a significant Christian substrate; one can derive a whole Islamic anti-history from them if one wants.
The Koran claims for itself that it is 'mubeen,' or 'clear,' but if you look at it, you will notice that every fifth sentence or so simply doesn't make sense. Many Muslims—and Orientalists—will tell you otherwise, of course, but the fact is that a fifth of the Koranic text is just incomprehensible. This is what has caused the traditional anxiety regarding translation. If the Koran is not comprehensible—if it can't even be understood in Arabic—then it's not translatable. People fear that. And since the Koran claims repeatedly to be clear but obviously is not—as even speakers of Arabic will tell you—there is a contradiction. Something else must be going on... Source: What Is the Koran?
Also scholars believe that there was no existing Islamic source material from the first century.
Wansbrough applied an entire arsenal of what he called the "instruments and techniques" of biblical criticism—form criticism, source criticism, redaction criticism, and much more—to the Koranic text. He concluded that the Koran evolved only gradually in the seventh and eighth centuries, during a long period of oral transmission when Jewish and Christian sects were arguing volubly with one another well to the north of Mecca and Medina, in what are now parts of Syria, Jordan, Israel, and Iraq. The reason that no Islamic source material from the first century or so of Islam has survived, Wansbrough concluded, is that it never existed. Source: What Is the Koran?
To summarize, only a minority of historians of early Islam doubt the historicity of Muhammad.
There is no doubt that Mohammed existed, occasional attempts to deny it notwithstanding. His neighbours in Byzantine, Syria got to hear of him within two years of his death at the latest; a Greek text written during the Arab invasion of Syria between 632 and 634 mentions that "a false prophet has appeared among the Saracens" and dismisses him as an impostor on the ground that prophets do not come "with sword and chariot". It thus conveys the impression that he was actually leading the invasions. If such a revised date is accurate, the evidence of the Greek text would mean that Mohammed is the only founder of a world religion who is attested in a contemporary source. But in any case, this source gives us pretty irrefutable evidence that he was an historical figure. Moreover, an Armenian document probably written shortly after 661 identifies him by name and gives a recognizable account of his monotheist preaching. Source: What do we actually know about Mohammed?
However, the doubts raised against the prophethood of Mohammed is listed below
Kalisch draws on the well-known work of Patricia Crone and Martin Hinds, whose criticism of the received version have a distinctly minority position in Koranic scholarship: It is a striking fact that such documentary evidence as survives from the Sufnayid period makes no mention of the messenger of god at all. The papyri do not refer to him. The Arabic inscriptions of the Arab-Sasanian coins only invoke Allah, not his rasul [messenger]; and the Arab-Byzantine bronze coins on which Muhammad appears as rasul Allah, previously dated to the Sufyanid period, have not been placed in that of the Marwanids. Even the two surviving pre-Marwanid tombstones fail to mention the rasul. Source: Scandal exposes Islam's weakness
The name Muhammad actually appears in the Qur'an only four times, and in three of those instances it could be used as a title – the "praised one" or "chosen one" – rather than as a proper name. Source: Did Muhammad Exist? (2012), p. 17
No record of Muhammad's reported death in 632 appears until more than a century after that date. The early accounts written by the people the Arabs conquered never mention Islam, Muhammad, or the Qur'an. They call the conquerors "Ishmaelites," "Saracens," "Muhajirun," and "Hagarians," but never "Muslims." The Arab conquerors, in their coins and inscriptions, don't mention Islam or the Qur'an for the first six decades of their conquests. Mentions of "Muhammad" are non-specific and on at least two occasions are accompanied by a cross. The word can be used not only as a proper name, but also as an honorific. The Qur'an, even by the canonical Muslim account, was not distributed in its present form until the 650s. Casting into serious doubt that standard account is the fact that neither the Arabians nor the Christians and Jews in the region mention its existence until the early eighth century. We don't begin to hear about Muhammad, the prophet of Islam, and about Islam itself until the 690s, during the reign of the caliph Abd al-Malik. Coins and inscriptions reflecting Islamic beliefs begin to appear at this time also. In the middle of the eighth century, the Abbasid dynasty supplanted the Umayyad line of Abd al-Malik. In the Abbasid period, biographical material about Muhammad began to proliferate. The first complete biography of the prophet of Islam finally appeared during this era-at least 125 years after the traditional date of his death. Source: Inventing Muhammad?