In the History and Taxonomy of Distilled Spirits There is ample evidence that distilled spirits were available during the time period you mentioned in a variety of places. We know that that Greek Alchemists developed the distillation processes about 1 AD and that a true distillation process was developed in Italy in the 1200s at the School of Salerno and Fractional Distillation was developed in the 1300s in Italy again. (Distilled Beverages Wikipedia) In 1313 there is evidence that Brandy had been made, although not widespread.
Then it seems in the 1400s, the doors open wide across Europe for distilled spirits.
Claims upon the origin of specific beverages are controversial, often invoking national pride, but they are plausible after the 12th century AD, when Irish whiskey and German brandy became available. These spirits would have had a much lower alcohol content (about 40% ABV) than the alchemists' pure distillations, and they were likely first thought of as medicinal elixirs. Consumption of distilled beverages rose dramatically in Europe in and after the mid-14th century, when distilled liquors were commonly used as remedies for the Black Death. Around 1400, methods to distill spirits from wheat, barley, and rye beers, a cheaper option than grapes, were discovered. Thus began the "national" drinks of Europe: jenever (Belgium and the Netherlands), gin (England), Schnaps (Germany), grappa (Italy), borovička (Slovakia), horilka (Ukraine), akvavit/snaps (Scandinavia), vodka (Poland and Russia), ouzo (Greece), rakia (the Balkans), and poitín (Ireland). The actual names emerged only in the 16th century, but the drinks were well known prior to then.
So, from about 500AD to 1300 AD, it was possible you could find distilled spirits, they were not widely available. Then in the 1300s distilled spirits spread across Europe and became widely available by the 1500s. Which one was actually the strongest? We'll never know but 90+% ABV was probably achievable with 1500s technology.