General Martok became a regular. Chancellor Gowron was recurring throughout TNG and DS9. The Duras Sisters (the less said about them the better) had some recurring appearances....T
Here is the thing, the show runners may be playing it safe by playing up iconic elements of the franchise, like Klingons, but as long as they do something new with them, I have no problem. We never had a reoccurring Klingon that we got see devlop over the course of several seasons, we never had a Klingon version of Dukat, most of the Klingon captains were genric bad guys of the week.