But, how would he explain the loss of McGivers if he was trying to cover something up? Then there's the issue of not warning anyone of Khan, it would be too big of a risk not to report Khan and his whereabouts, otherwise something similar may happen to another ship.
It would be trivially easy for Kirk to tell further lies to improve on his original lie intended to protect Khan. He often lied to his superiors, or left things untold; his logs appear to be dictated well after the fact, with significant omissions and interpretations of events.
Kirk wouldn't be thinking in terms of Khan being a risk to others, not if he were marooned on a planet nobody would visit (remember, the Botany Bay
was found by chance in a region of space nobody visited any more - Ceti Alpha would probably be nearby). It just didn't occur to him that others might also seek for the solitude of the location, and that a secret Federation research facility would be established in the neighborhood.
I don't think breathable air is necessarily a requirement. The Genesis device could program the matrix so that breathable air was included.
But if that were so, the universe would have been teeming with suitable lifeless worlds. No need to search for one: Regula itself would do.
The very fact that the Reliant
apparently spent ages searching through systems that had a desert world listed is proof enough that the requirements were extremely specific, and that the nicely oxygenated Ceti Alpha V/VI met those precisely. It must have been hellishly difficult to find a planet devoid of life but with oxygen - in essence, a world that had died, rather than a world that had never lived.
"You boys have to be clear on this. There can't be so much as a microbe or the show's off."
So that leaves the second theory: that Marcus opposed to the killing of any lifeforms found, but by definition could not complain about those not found, or those that were unfindable.
Although the third theoretical possibility is that the Genesis experiment, while necessarily successfully transforming the planet, would produce inconclusive results if the planet happened to boast life before the detonation already. And that's what it most sounds like.
Basically, then, Starfleet just didn't have the sort of sensors that could have performed the mission. But they didn't know that in advance, so we can't really blame them.
I wonder... Could Kirk have set up an apparatus that hid the presence of Khan and his colonists? Something like the duonetic damper of DS9 "Paradise", perhaps? That would be a good way to ensure that Khan stayed marooned and unbothered by the authorities.