It actually makes a bit of sense that Marcus and Khan would jointly create a false identity for Khan that would be patently false, i.e. immediately recognizable as highly suspicious.
After all, Marcus wanted a war with the Klingons, and everything Khan did under the Harrison alias (until he confided in Kirk and tried to enlist the hero's sympathies) helped Marcus in reaching that goal. We would do well to assume that Khan's actions, including the seemingly spontaneous "terror bombing" and "penthouse massacring", were jointly planned to force this unlikely situation where a Starfleet patsy would chase a rogue agent to Klingon space, get killed by the Klingons, and make the Klingons a) angry and b) look guilty for harboring a criminal and then destroying a Starfleet ship on a just mission.
But why settle for this man being a rogue agent? Associating his evil deeds with Starfleet would make Starfleet look bad. Better make him a "rogue agent" instead - a pretender who doesn't even exist in Starfleet records.
If Kirk could access the records, anybody could (or conversely, if Marcus really wanted them secret at all, he'd first make sure they were secret from Kirk). But who knows that John Harrison was supposed to be a Starfleet employee? Kirk, Spock, Pike and the people at the Daystrom Building penthouse - in other words, dead people. When Marcus gets his war, the Federation gets the story that the hunted criminal was but an impostor, and Starfleet doesn't get a blemish for trusting the wrong man.
Okay, so this gives "stretching" a whole new definition. But only because creating a year-long false backstory is not the most efficient and plausible way to make the public think this man was an impostor...
The simpler explanation was that there was no need for a convincing backstory, because everybody who knew about John Harrison would be dead within days (if not minutes!) of learning about him. John Harrison only needed to convince long enough to get the chosen patsy (Marcus no doubt had Kirk in mind from the get-go) to go after him.
Timo Saloniemi