I take your point, but it's not just that they fail to make the connection for so long; it's that when they do, it turns out that all four of K/S/Mc/Scotty remember him very well and even have opinions about him. "Sneaking admiration" from Scotty, "He was the best of the tyrants," from Kirk, etc. Even in 1966, the idea that there would be no photos of Khan floating around was preposterous; it's even more belief-stretching today, of course.
For me the big flaw behind "Conscience of the King" - also remedied and overshadowed in a good way by superb dialogue, a compelling story, and excellent acting, just like "Space Seed" - is similar, but the inability to confirm the identity of an infamous colonial governor/murderer pales in comparison to not grokking that you just awakened the "absolute ruler of a quarter of" Earth. Just on circumstantial evidence alone it was pretty clear that Khan should have been tossed in the brig with five security guards with phasers on him (like his escort to the hearing at the end) about 10-15 minutes into the episode.
I might have towed the Botony Bay to the least populated planet closest to the Klingon border, or SHQ.