Missions are fun... after about the first go around, try 10 times on the Fed and 3 on the KDF, it get's repetitive. Been here since OB yes the game has changed... slightly, mostly graphically, content not so much. Only a hand full of mission have ever been edited for "new" approach. Mostly Doomsday was redone the best... ohh Sthal still waiting on a KDF side of that mission like you mentions ohh so long ago. To quote Scotty, "I know this ship like the back of my hand". I left for about three to six months and I know the missions still.
Yeah I agree the missions can be repetitive and samey but it would take a major redevelopment of the mechanics of game to implement a more varied mission system. It's the same for every game I've played tho, from XCom to uncharted - prebuilt missions are very similar - which is why so many choose DEATHMATCH lol
Although I have limited PvP exp on STO at the moment those challenges are the way to go imho, for real variety and unpredictability.