I think part of the problem is that the RTS features these characters, so even when it kills a few (like Terenas Menethil) it offers up a few more. But the MMO features us, ultimately, so when we put down Lady Vashj or Arthas, there's no immediate replacement. To be sure, there have in fact been tons of new faces over the course of World of Warcraft - Ragnaros, C'thun, Nefarian were all first introduced in classic WoW, not the RTS. The problem is, we introduce these characters and then, well, we dispatch them. Sometimes, like Ragnaros, our first encounter with them isn't a final one, but even if we know they'll eventually be back, it's not like their luck will hold out forever. I called this the "Joker problem" once, and to a degree I think it is an issue for the MMO.
However, does it follow that we need an RTS to create stories? Since I think Mists of Pandaria did an amazing job of building up the story, and in fact I'm really much more of a Cataclysm booster than most, I don't agree with that idea. In fact, in many ways, WoW has done more to broaden and expand the Warcraft setting than the RTS ever did.