|17th century painted icon (ironically) representing|
the "Not Made by Human Hands" tradition;
the Greek letters in the halo indicate that it
is an acheiropoieton.
To be honest, the early Middle Ages should not have had to deal with this dilemma, since the story of Veronica is not found in the Gospels and is not readily known until almost the 13th century. In fact, it is our old friend Gerald of Wales who first records anything in the West about the veil, which he says he saw on a pilgrimage to Rome in 1199. (Gerald is the first to point out that the name "Veronica" is Latin "vera+icon"; that is, "true+image.")*
Authentic or not, it was the start of a trend of cloths that showed the face of Jesus without having been made by human agency. Icons such as this had a name, Acheiropoieta, "not made by hands" (Greek ἀχειροποίητα).
Despite the "not made by hands" label, many items that fell into this category were made by human hands, so long as those hands were holy, or the subject was an acheiropoieton. Saint Luke was said to have painted a portrait of Mary when he visited her. If this image survived, it would be an acceptable icon. Also, human reproductions of Acheiropoieta were considered by some to be as sacred as the originals, and as acceptable in the face of the iconoclasm controversy.
An eastern Church Council of 836 declares certain items to be legitimate Acheiropoieta: the Image of Edessa, a square of cloth containing the face of Jesus; an image in Lydda (now Israel) of the Virgin that appeared miraculously on a pillar in a church; another image of Mary in Lydda that appeared in another church. Unfortunately, there was no Church Council of 836, and the document is considered fraudulent.
Acheiropoieta are usually considered to have miraculous properties. On the Island of Cyprus there is an Acheiropoietos Monastery, named so because of an Acheiropoieton that miraculously moved from Asia Minor in the 11th century to save itself from a Turkish invasion.
*To the Middle Ages, this was proof that the world is composed of patterns and symbolism. To later historians, this suggests that "Veronica" was an ideal name made-up expressly for this anecdote.