Following a report of a planetary distress signal that is recieved by the Astropath Transcendant, the message was that whole planets are being destroyed by a new techna envisioned created and embodied by a Necron Invasionary Fleet. Coming from deep within the Koronous Expanse, the Necrons are systematically stealing energy and life forces from whole planets rendering them dead and utterly useless. Stopping at Footfall, the Explorers recieve a warrant along with two other Rogue Trader Dynasties to advance through the Koronous System, use diplomatic relations with the attempts of stopping the Necron Fleet and or by all means necessary, find a way to stop the threat and destroy the Necrons. The Necrons are using technology within a new starship named Tesseract Labyrinth in which is a Metal Cube that can use warp energy to withdraw planetary life forces into the Labyrith and continue on till the seething and hate inspired Necrons have utterly destroyed everything.

I was thinking that on Footfall, the game could be devised into nine sections. The Boneyard, The Chapel, The Hab Fanes, Lieges Court, The Red Schola Shield Shrines, The Spire of Intoxicants and The Xenosium. If these places sound similar they are. The locations have been released in Lure of the Expanse but using a rough outline I was thinking each of the Explorers could have started a individual story line from these initial places of Footfall. I was thinking that finding a slave girl of psychic ability or Mutant named Alehsai accompanied by a human renegade named Savag would be the missing piece that can fortell a way to stop the Necrons. I could use each of the above place for around 5 to 10 acts five pages each to continue the story line. I could use several of the supplements factions to contest or aid in the players trying to obtain the mutant girl or stop them. Black Brotherhood and Astral Knives come to mind maybe the girl was going to be sold to the highest bidder of the other competiting Rogue Trader Dynasties. They have to get the girl from The Tutors and the Drusians are there to assist the players.

Maybe making the girl evil and starting a mutiny aboard the ship, would be another encounter that the players would have to undergo. A encounter of the Necron starships and an chapter dedicated to plant exploration and evacuation because the Necrons will be heading towards this planet and the players leave the planet just in time to be boarded by the Necrons. Eventually I wanted to give it a Star Trek Borg feeling to it with exploring the Labyrinth and maybe stealing the Senior Captain and the girl or maybe Savag turning on the crew. Is this game sound? Thoughts feelings?

One thing I would change is instead of calling the doomsday ship "tesserect Labrynth" I would instead call it something else and say it is based on an upscaled version of a tesseract labrynth, because a tesseract labrynth is an already established peice of necron technology.

What Cryhavoc said.

Also, Necrons don't use the warp. Their own superscience should do well enough on it's own.

Necrons Possess Magic Murderbox, kill people.

I'm not sure the Necrons need a magic artifact. As Uncle says "Magic must defeat Magic" which inherently limits your players- They might have more fun if it were just an ordinary fleet of incredibly deadly murder machines, since there are far, far more ways to defend against that sort of thing. Maybe they'll make a deal with Space Marines, or the Eldar, or try to use Orks as cats-paws while they rally a fleet to strike at an unprotected flank….

The Explorers recieve a warrant along with two other Rogue Trader Dynasties to advance through the Koronous System, use diplomatic relations with the attempts of stopping the Necron Fleet and or by all means necessary, find a way to stop the threat and destroy the Necrons.

Wait, the Explorers are given their warrant with the specific purpose of stopping the Necrons? It's worth thinking about who gave them this warrant, and why- Warrants require the approval of the High Lords of Terra, which means you need a fairly heavy hitter in one of the major powers (Admech, Guard, etc) in order for your Warrant to get processed. You should specify to your players that they should include in their backstories what makes them so great that the Imperium would give them essentially infinite authority in dealing with this crisis.

I was thinking each of the Explorers could have started a individual story line from these initial places of Footfall.

This is a good idea- Giving every player their own unique goals is always a good way to increase interparty interactions and help avoid the RPG cliche' where the five players are essentially a hive mind. However, it's worth noting that although you should give the party their own questlines, never ever ever actually split the party. It slows the game down hugely. Instead, give them their unique information before and between games.

I was thinking that finding a slave girl of psychic ability or Mutant named Alehsai accompanied by a human renegade named Savag would be the missing piece that can fortell a way to stop the Necrons.

As with the above thing about the necrons having a magic artifact, I feel like prophecies are a nuisance and inhibit freedom. It'd be an okay plotline for a D&D game, but Rogue Trader is, again, a game mostly about freedom.

Similar to previous posts i have a few comments - 

• Avoid the warp when it concerns necrons: they do not like the warp, they do not travel in the warp and they do not use the warp in their technology. The warp is absolute chaos, raw unbridled creationism. Necrons do not like chaos, they like absolutely regimented order and they like to drain the life force out of things. As you can imagine, the two are anathema to each other.
  I would however point to the Word Bearers novels within which a necron lord makes use of an artifact called a Nexus Arrangment http://wh40k.lexicanum.com/wiki/Nexus_Arrangement#.UNGQqTUZcSE which creates a blanket of anti-warp around a star system, thus preventing those that require warp travel from entering or leaving the system. Perhaps an artifact along those lines that also drains the life force of anything living within a system. Remember that this was back when necrons weren't rubbish and hijacked the eldar webway to travel but instead could just fold space-time and instantly move their tomb ships wherever they wanted - as such the power level of the artifact may be a bit much for the players to contend with.
• Warrants are a big deal. I wouldn't let a rogue trader be handed one and told "stop the necrons, you are my only hope obi wan ke…. wait wrong setting'. Warrants tend to be a bit more vague in their wording - focussing on supporting trade routes between certain sectors, providing support to guilds and dynasties or even aiding the admech or imperial navy in military endeavours. If the high lords of terra were worried enough about necrons in an area of space outside of the imperium, then theyd send space marines, the imperial navy and admech assets such as titans and ordinatus to deal with it, not a handful of rogue traders. That said if your rogue traders warrant's covered the area of the Koronus expanse from back when it was first colonized, it would make sense that either military commanders of Port Maw, Battlefleet Koronus or the Calixis sector have called them in for support in operations against the Necrons.
• Prophecy sucks. It leeches the fun out of it for players, reducing their actions to feeling like rail-roaded decisions by the GM. Whether the GM actually is rail-roading them is besides the point. The only time i like prophecy in my games is to act as a distraction to the players, and if they focus on trying to avert the prophecy i conspire to make it so that THEY are the ones who enact it. Examples such as "The house of Red and Gold will fall to the Masked ones" ending with the players infiltrating a masked ball in order to discover who is going to assasinate the lords and ladies of the house, but end up causing a fight that ends with them killing everyone.
• I'd srongly suggest having other Xenos involved in the plot, simply because human technology is entirely inneffectual versus necrons. Some eldar with a score of ships that can be pledged to the attack on the doomsday ship, or perhaps some orks who can be tricked into attacking at the same time - basically the players need every single bit of help they can get.