None of that matters. In the context of the film, Khan knew the planet exploded. Chekov and Terrell do not question or contradict this, and the viewing audience doesn't bat an eye about it either since it doesn't affect the plot of the movie. Feel free to think Khan made it up all you want, but since there's no reason for him to lie about it, it's a moot point.
And exactly since it's moot, we have zero reason to believe Khan. The default position would be that something possible happened, while the impossible should only be brought up when there's a pressing reason to do so. Such as some sort of a confirmation that Khan is right.
(The other characters would have no reason to contradict a madman, either. He lives in his own little bubble where e.g. Kirk is to be blamed for stuff, and we see what happens when Chekov tries to contradict him on that.)
You don't know what kind of planets the Ceti Alpha system contained. All we know is that they had to be "completely lifeless." For all we know, Ceti Alphas 1 through 6 were all potentially suitable planets. Only a scan of all the planets would confirm whether they were or not. We just happened to come in at the point where they were scanning Ceti Alpha 6(5).
All planets in the Sol system are lifeless, save for Earth. Only a madman would head for Earth to look for a lifeless world. Yet here our sidekicks are, scanning a planet with free oxygen in the atmosphere.
Unless Ceti Alpha and Regula are next-door neighbors, the
Reliant would have no reason to do a "search" for a generic lifeless world that would lead them to CA. She could simply fly to the neighboring system, which
must have one of those. Flying to a distance of three travel days would be an idiotic complication to the Phase III experiment, then. But if planets that have free oxygen and nevertheless have to be lifeless are the only suitable ones, then the sidekicks have every excuse for a prolonged and exhausting search, since the combination is so unlikely (indeed, it probably hinges on Trek Milky Way being so full of life that there are failed ancient terraforming experiments lying about). Certainly a system containing two or more of the sort would be an unlikely find.
1. The Reliant wasn't scanning for recently exploded planets.
And indeed we have no reason to think she was scanning for planets of any sort. From what we observe, the prodecure would appear to be "enter standard orbit over a planet on the list of candidates,
then scan for life, Y-> move to next system and repeat, N-> inform the Marcuses and return to fetch the Genesis device".
2. What happened in a TOS episode that took place 15 years before TWOK is hardly a "primary source" of information.
In what sense? Starfleet appears largely unchanged between spinoffs in the 22nd and 24th centuries. Why worry about 15 years?
I'm pretty sure that's not true.
Orbits around target planets involve the acceleration of one gee, give or take. That's "idling" for a starship's engines. Orbits of planets around stars involve speeds of a few dozen kilometers per second. That's less than "fine tuning" for a starship approaching on a 23-min-14-sec-from-Terran-system-limits-to-Earth-on-impulse beeline.
Really, associating the way Starfleet flies in space with the way NASA flies in space is even more misleading than associating the way the Concorde gets from Paris to New York with the way thistledown does.
Timo Saloniemi