A: Beni Suef Governorate, Egypt
The oldest surviving Arabic papyrus, and the oldest dated Arabic text from the Islamic era, PERF No. 558, dates from 22 AH (642 CE). Found in Heracleopolis (Herakleopolis Magna, Ἡρακλεόπολις) in Egypt, it is a bilingual Arabic-Greek fragment, consisting of a tax receipt: "Document concerning the delivery of sheep to the Magarites and other people who arrived, as a down-payment of the taxes of the first indiction."
"Features of interest include:
"The first well-attested use of the disambiguating dots that would become an essential feature of the Arabic alphabet;
"It begins with the Islamic formula "Bismillah ir-rahman ir-rahim" (In the Name of God, the Merciful, the Compassionate)
"It records the date both in the Islamic calendar (Jumada I, year 22) and in the Coptic calendar (30 Pharmouthi, 1st indiction), allowing confirmation of the traditional date of the Hijra.
"In Greek, it calls the Arabs "Magaritae", a term, believed to be related to the Arabic "muhajir", emigrant, often used in the earliest non-Islamic sources. It also calls them "Saracens".
"After excavation, the papyrus was put in the Erzherzog Rainer Papyrus Collection in Vienna" (Wikipedia article on PERF 558, accessed 12-29-2012).
In December 2012 a list with descriptions of "Dated Muslim Texts From 1-72 AH / 622-691 CE: Documentary Evidence For Early Islam" was available at Islamic-awareness.org.