In Did Muhammad Exist: An Inquiry Into Islam's Obscure Origins, Robert Spencer quotes from the Doctrina Jacobi, which contains "[o]ne of the earliest apparent mentions of Muhammad." "Probably written by a Christian in Palestine between 634 and 640 - that is, at the time of the earliest Arabian conquests and just after Muhammad's reported death in 632 - [the Doctrina Jacobi] is written in Greek from the perspective of a Jew who is coming to believe that the Messiah of the Christians is the true one and who hears about another prophet risen in Arabia." I have added paragraph breaks:
When the candidatus [that is, a member of the Byzantine imperial guard] was killed by the Saracens [Sarakenoi], I was at Caesarea and I set off by boat to Sykamina. People were saying "the candidatus has been killed," and we Jews were overjoyed. And they were saying that the prophet had appeared, coming with the Saracens, and that he was proclaiming the advent of the anointed one, the Christ who was to come.
I, having arrived at Sykamina, stopped by a certain old man well-versed in scriptures, and I said to him: "What can you tell me about the prophet who has appeared with the Saracens?" He replied, groaning deeply: "He is false, for the prophets do not come armed with a sword. Truly they are works of anarchy being committed today and I fear that the first Christ to come, whom the Christians worship, was the one sent by God and we instead are preparing to receive the Antichrist. Indeed, Isaiah said that the Jews would retain a perverted and hardened heart until all the earth should be devastated. But you go, master Abraham, and find out about the prophet who has appeared."
So I, Abraham, inquired and heard from those who had met him that there was no truth to be found in the so-called prophet, only the shedding of men's blood. He says also that he has the keys of paradise, which is incredible [i.e., not credible].
Spencer spells out the implications:
One thing that can be established from this is that the Arabian invaders who conquered Palestine in 635 (the "Saracens") came bearing news of a new prophet, one who was "armed with a sword." But in the Doctrina Jacobi this unnamed prophet is still alive, traveling with his armies, whereas Muhammad is supposed to have died in 632. What's more, this Saracen prophet, rather than proclaiming that he was Allah's last prophet . . ., was "proclaiming the advent of the anointed one, the Christ who was to come." This was a reference to an expected Jewish Messiah, not to the Jesus Christ of Christianity (Christ means "anointed one" or "Messiah" in Greek).