Even in the case of Kahn or Charlemagne this is not a problem. Because at least some of their wives are also UGAs too. So then that would be a paired couple. (this is also contingent on them leaving far enough in the past that they are UGAs)
Regarding your second question. That gets to the heart of the confusion. You are trying to transfer your instincts about genetics to genealogy that does not work, and will confuse you every time.
The difference is that m-MRCA and y-MRCA are singular. UGA (do not confuse this with MRUGA) are plentiful and every where. Even MRUGA is not singular but arises simultaneously everywhere. There is no reason, however, to think Adam and Eve must be MOST RECENT, so UGA is just fine.
This figure is helpful…read it in detail and more of this will make sense…
Genealogical ancestry is not genetic ancestry. Illustrating the story in the text, we show a cartooned pedigree, a genealogy, from past (top) to present (bottom). Squares and circles denote men and women, respectively, with lines indicating parentage. Red and blue individuals are those in the genetic lineages to a single ancestor, Mito-Eve and Y-Adam, respectively. In contrast, every individual with a black border is a common genealogical ancestor of all those in recorded history (grey box). The Scriptural Adam and Eve (the black box and square) are created from the dust and a rib less than 10,000 years ago, have no parents, are in the Garden of Eden (black box), and are genealogical ancestors of everyone in history. This story is entirely consistent with the genetic data.