I think STO would greatly profit if there was a similar feature like in Champions Online. It would give the game a certain degree of unpredictability, which would make the game much more exiting.
Our Nemesis should appear very rarely, to be shure it doesn't get annoying.
There should be a way to get rid of this nemesis, like completing a rare DOFF espionage assignment chain, for example, which would unlock the whereabouts of the nemesis. Once defeated we should get the chance to create a new Nemesis.
It is an aspect I found very original in CO and seemed easy enough to implement but could it work for STO, with its many races and technologies? I do think it could make for a very cool series of FEs that pop up from time to time.