If I understand correctly, and I believe I do, the validity of the Pope rests on the apostolic succession, ie the concept that Peter was the first Pope and selected his successor and so on, so that the current Pope can trace his validation all the way back to Jesus. Is this a historical fact? Do we know anything about Peter’s successors, the early Popes? If not, when is it believed that the Papacy got started? How far back does the history go?
I know there was that multi-Pope business a half-dozen centuries ago, but let’s ignore that for now.
The apostolic succession speaks not to the validity of the pope per se, but rather to the validity of any bishop, of whom the pope is one. All bishops in the Orthodox and Catholic churches (and a few others, such as the Orientals and some Protestants) can trace a chain of ordination back to the apostles. I found a decent article at Catholic Answers that quotes extensively from the early Fathers regarding the succession.
I believe that the only Protestant church where the Apostolic Succession is much of an issue is the Church of England (a.k.a. Episcopalians here in the United States). Although they claim to have maintained the Apostolic Succession intact through the days of Henry VIII, the Roman Catholic Church and the Orthodox Churches do not agree with them, and therefore do not consider their sacraments valid. The Orthodox Churches and the Roman Church (including the uniate Eastern Rite churches, which is what I’m guessing you mean by “Orientals”), although separated on several issues, recognize the validity of each other’s sacraments, since the chain Apostolic Succession was never broken, despite the schisms.
The Oriental Orthodox are the communion consisting of the Copts, Ethiopians, Eritreans, Syrians, Armenians, and Malankara Indians. As for your statement about Catholic and Orthodox mutual recognition, it is not quite correct. The Catholics regard the Orthodox as having valid sacraments, but the Orthodox are officially agnostic on whether Catholic sacraments are effective or not. Properly, an individual coming into the Orthodox will be baptized, no matter what denomination they are coming from, but it is the case that occasionally an individual coming from the Catholics or high-church Anglicans will be received by Chrismation (annointing with holy oil). This is not to be construed as an acceptance of the efficacy of the heterodox baptism, but of grace retroactively filling the empty form of the baptism, which ideally should have occurred with triple immersion, in the name of the Father, Son, and Holy Spirit. If the person was baptized with a single immersion, or in the name of Jesus alone, etc., then the person must be given an Orthodox baptism.
Apostolic succession in general is viewed differently from the Catholics by the Orthodox. It is important to be ordained by someone who himself has apostolic succession, but this ordination must take place inside the Church. The Orthodox see the Catholics as having left the Church, and so while they may have maintained valid forms, the Orthodox cannot say if they have grace or not. The same applies to the various small vagante groups that have split from the Orthodox: they may have maintained technically correct apostolic succession, but having cut themselves off from the Church are treated as any other heterodox body.
To answer another part of your question, records are kept. I once had a (Episcopal) priest who had a chart on his wall that showed his name, with a link to the name of the bishop who ordained him, with a link to the name of the bishop who consecrated him, and so on, back through the centuries, to the apostle Matthew.
Now, I don’t know well the church records were kept nineteen centuries ago, but theoretically any Bishop should be able to trace his succession back to the original apostles like that.
It should also be pointed out that popes do not select their successor - the Congress of Cardinals selects popes after the previous one buys the proverbial fiefdom.
IIRC some Lutheran episcopates (for some reason one or more of the Scandinavian branches seems to come to mind) did maintain a link of some kind to the succession.
In the case of the Anglican communion, the RCC officialy decreed in 1896 that on procedural grounds they considered the AC to have broken the succession.
If an Episcopal priest can trace his lineage back to a pope who lived 500 years or so ago, that gives the full lineage if you believe the RCC’s history. Many on the list of early popes have no other supporting basis. The supporters of the “Pope Joan” theory have also found numerous holes in the papal history of that era. Actual history it isn’t.