I don't have specific experience of the Czech Republic, but I believe this to be an exaggerated myth. I stopped in many LBS's along the route, in small towns in Bulgaria and Romania, and was having some real problems with punctures/tyres at the time. Not once did I find them to have only 'racing' tyres - most had a good selection of 700c tyres, of varying width and tread. OK, so not a perfect pair of Conti Top Touring or whatever your preferred set is at home, but perfectly adequate. This idea that slightly out of the way places only have 26" tyres and racing 700c is simply not true.
