"Those countries did not exist forty years ago."
Translation:Ty země před čtyřiceti lety neexistovaly.
Is this in a way an exception from the rule "always genitive after high numbers" or does this rule not exist after prepositions?
lety here is instrumental plural and not nominative, because that case is required after the preposition před.
The rule that genitive is used after numbers higer than 4 only holds for nominative and accusative. In oblique cases (any case other than nom/voc/acc), both the numeral and the noun take the plural form of the corresponding case (notice here that čtyřiceti is an inflected form, the base form being čtyřicet).