Storytelling in STO has evolved a great deal since launch. We've seen Cryptic experiment with new Story/Mechanics releases with the first our FEs with mixed results. Writing the same story to fit two disparate factions is difficult enough and they did not always succeed, the 2800 felt forced for the KDF. Then there were the exclusive missions for the KDF that did a better job of it, if completely isolated. Many, myself included, regard the Fek'lir arc as the best in the game.
The remastered missions was another step forward that I hope they continue with on both factions, even i one was a long sales pitch for the KDF (The Doomsday Machine). In the last year I have seen Cryptic do some interesting things with story telling, making it less obvious and allowing you to...wait for it...discover it! Storytelling via the Duty officer System. The Catian Diaspora chain tells of the schism between everyone's favorite felines. Its not traditional but it got me interesting in searching for the next assignment in the chain. There are a few other examples of this and I applaud the attempt.
The latest developments are Nukara Prime and New Romulus. Adventure Zones appear to be the future for the game and while Nukara only hints at story, a means to an end, New Romulus and it's reputation system tries to bridge the gap, telling the story of the planet's desperate residents and the forces arrayed against them. Each tier rewards you with a cutscene that furthers the story a bit more, enticing you to continue to find out what happens next. Tier unlocked instances give you snipets that link events together, the Tier one instance for example bridges the gap between "Cloaked Intentions" and New Romulus.
Cryptic is learning and while they are focused on play, aesthetics, and mechanics, they have not forgotten future story. The older stuff might not be the best but it is my hope that they will go back and remaster some of it.
My two EC.
Also known as Gingie(In game) Sskald(Gates of Sto-vo-kor)