Remember what happened the last time you let me loose on a bare idea?
But lets see now...I'm just trying to recall an old episode of Dr Who when all incarnations of the Doctor met up to stop a threat which spanned all of the time/space continiuum.
How about this, the Lexington of your game runs into the USS Lexington of the Federation Time Fleet. The crew are recruited for a special mission (part of the Temporal Cold War...why not) and in the course of the mission, encounters all incartions of the starship Lexington past, present or future...that's where having a brief precis of previous ships with the same name so that you can co-ordinate such adventures. Each Lexington has to complete one part of the puzzle (of course the Timeship crew can't reveal every piece to everyone for fear of polluting the timeline). Well of course the inevitable disaster happens when the Timeship Lexington is destroyed by the enemy forcing the crew of the present Lexington to take charge of the operation because they received every piece of the puzzle which includes a trip back to WWII to save the aircraft carrier Lexington from a Kamikaze attack in 1945...
Most of this is off the top of my head but I'm sure a genius like Zymmer can iron out the bumps.
Arise, arise, Riders of Theoden!
Fell deed awake: fire and slaughter!
Spear shall be shaken, shields be splintered,
a sword-day, a red-day, ere the sun rises!
Ride now, ride now! Ride to Gondor!
Theoden King: The Return of the King