Heh, they go back as far as is possible, Ami Hund. I've got legendary rulers of Greek city-states in the 1200s BC. I may complain about having to translate French Heraldese, but the headaches from that were nothing in comparison to compiling all the rulers of Republican Rome - two consuls a year for nearly 500 years, not including a fair number of replacement consuls and dictators, and of course Roman names were ludicrously long anyway. It tooks months just to do that alone.
For the most part, the only European states I don't have done are those that were centered on African or Asian lands, most notably the Byzantine and Turkish states. Although Constantinople/Istanbul is in Europe, these nations usually possessed more territory in Asia than in Europe, so I will compile them when I get around to doing Turkey (which, being physically mainly in Asia, I haven't gotten to yet). There are a few minor gaps here and there, such as the cantons of Switzerland before 1700, or the burgomeisters of Frankfurt and Lubeck before 1500 (or of any other German Free City other than Hamburg or Bremen, such as Augsburg or Ulm, for which I have no information whatsoever). The most irritating gap, the Bishops of Metz, Toul, and Verdun, was recently filled, although I only have first names for many of them.