"Those countries did not exist forty years ago."

Translation: Ty země před čtyřiceti lety neexistovaly.

[alturing]

Is this in a way an exception from the rule "always genitive after high numbers" or does this rule not exist after prepositions?

[relox84]

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).