The two missing legions are one of the single greatest mysteries in Warhammer 40,000 today. Ever since the II and XI were mysteriously left expunged and empty during the Index Astartes era, fans have speculated as to just who these primarchs were and what role their legion might have played. Others have wondered why they might have committed so grievous a sin as to be erased entirely, and what was the ultimate cause for their downfall prior to the civil war which fragmented the very galaxy itself. It's just one of those tantalizing hints which often leaves fanatics irate and wondering what in the hell might be hidden just out of sight.
Now, veterans will know there have been a few screw-ups and old lore tidbits which have been left over from past authors. The Valedictors were infamously listed as being led by a primarch thanks to a severe miscommunication, and the Rainbow Warriors were once listed as a First Founding chapter in the days of Rogue Trader, only to be largely omitted from many future releases. Some sources have alleged that the legions were both killed off and never replaced thanks to their dishonor, a move mimicing ancient Rome's Damnatio Memoriae.
The more modern take upon the Great Crusade and Horus Heresy itself has continually alluded to some great disaster or even betrayal. Time and time again it has been suggested that the Space Wolves were unleashed, while a few others have strongly hinted that generic degradation was a key part in their eventual erasure. While ideas have repeatedly gone back and forth over and over again, with some supporting an active role in the Crusade while others suggest they failed to even become a true legion, each suggests that they are no longer about.
So, old and new lore is based upon the idea of their complete annihilation, so how could you build an army based upon them? Simple: The Emperor lies.
He tends to lie a lot, often for his perceived benefit of humanity over everything else, but we have seen it time and time again. The Imperial Truth was the big one, but then we had hints of him lying to his own sons. In fact, the Emperor went so far as to telepathically erase certain facts from them, as proven in Vengeful Spirit, keeping his source of power hidden from them. So, if he's willing to erase that one detail, why not the existence of two legions which might be very important to his plans?
Think about it for a moment. Each legion was intended to carry out a single role within the Imperium or Great Crusade, from the fearmongers to the builders to the annihilators; so is it not so unbelievable that two might retain so great a role they would be hidden from all others? Some would argue that the Alpha Legion ultimately fulfilled this role as His Majesty's Hallowed KGB, but they were ultimately very terrestrial in nature. Like all other legions their role focused upon conquest of new worlds, the annihilation of xenos races and reuniting humanity. What if each legion needed to be left completely forgotten to history in order to play some great part in the Emperor's plan, or defend his realm against threats from beyond?
We already know that the Webway was a core part of the Emperor's plan just for starters, and even in its early years it was hardly a perfected science. Even without Magnus' ill advised efforts screwing things up, there was always the perpetual risk of daemonic incursions, corruption or the degradation of the ancient network. This would require a force to continually patrol each route, slowly expanding throughout the Imperial Webway and guarding it against all invaders. While the Thousand Sons might well have been suited for this role, what we see in A Thousand Sons does subtly suggest that their slow instability may not have been a mistake. If what we see in that book was to be believed, Magnus' role required him to be bound to the Astronomican itself, having severed all earthly ties and serving as a psychic lighthouse for travelers. Such an act would leave a legion bereft of their father - and may even give them reason to rebel if they saw his intended plan - or even cause difficulty in maintaining gene-seed stability. Even if you don't accept that however, a more numerous and more specialised force to accompany the Thousand Sons is hardly out of the question.
Still, ignoring the Webway, what else is there? Well, how about extra-galactic threats or creating a bulwark against outside invasions. Several Imperial Armour books - notably the Badab War volumes - have repeatedly emphasized that the Imperium made various expeditions beyond the galaxy's edge. The Marines Errant were part of several such operations, and the
Even if you don't like the idea of them patrolling those areas and merely defending an empty void, there are other opportunities to be had here. Perhaps the Emperor tasked them with hunting down sleeper ships lost during the downfall of the Human Empire or even bygone relics from eras past. They might have been tasked with recovering ancient pan-galactic fortresses leftover from humanity's golden age, or even silencing ones of xenos origin before they can become a threat. That or, if you want to go for the most obvious excuse, claim they've been spending the last nine thousand years kicking the living hell out of the Tyranid Hive Fleets.
Of course, there is a third option which may or may not work depending upon what berserk buttons you have about the lore; you could have them permanently stationed in the Warp, carving out strongholds against the forces of Chaos. Yes, this is going against a point I have personally long railed against - That Games Workshop has forgotten that no mortal can survive physically entering the Warp. It's something they've broken time and time again, from Draigo's rampage to the Fire Hawks raiding Nurgle's Garden to turning many previously conceptual or metaphysical ideas into literal locations. It's been going on for years now yet one of the most frequent commenters on here - grdaat - pointed out, they never do anything with it.
The Imperium seems to actively ignore the fact they can happily launch successful crusades right into the realm of Chaos itself, beat the daemons on their home turf and slowly purge the realms of Chaos themselves. They could be sending wave upon wave of Imperial chapters right into Nurgle's garden torching everything in sight, or even just causing enough of a distraction to stop the daemons emerging in the materium. So, if this bit of canon defilement doesn't make your blood boil, you could have them doing exactly that. Imagine close to a hundred thousand astartes hunkered down behind vast psychic fortresses or defended by Gellar fields, fighting an endless tide of daemons to hold onto humanity's few strongholds in the Warp. Actually, thinking of lore of late, they probably wouldn't even need Gellar fields given how tame the Warp is these days. Furthermore, as time is meaningless, some could have been doing this since long before the Heresy, or even be completely unaware that Horus turned traitor at all. There's certainly a lot of leeway on offer with this one if a writer is inventive enough about such things.
These are just three examples, and there's certainly many far less insane ideas you could drum up. By simply going with the fact that they would have held an important role no other legion fully fulfilled, you can mold them into any number of various ideas or concepts. If you have a few ideas you'd like to list or even criticise those brought up, please feel free to list them in the comments. As always, other viewpoints are always welcome in these "what if?" articles.