There's no real reason why they couldn't go and retcon a bunch of old evolution methods. It's difficult to keep track of them all, and the game often doesn't even give you any hints as to how they evolve, forcing people to go look them up online.
That would be very nice, and they have done it before, both with Eevee in XD and Feebas as of Gen V. In both cases, however, the methods had been changed because the mechanics had changed. No, the issue of evolutionary methods and mechanics is more philosophical in nature, I think.
In the anime, Eevee should have been able to evolve into Sylveon from the beginning, because what Amie provides is simply a more in-depth foray into affection and bonds. The issue here is that this is something that's not easily shown in the games, but something wouldn't have been an issue in reality - the anime and manga in this case. Eevee's evolution into Sylveon has the same basis that it's evolution into Espeon and Umbreon has; it's stronger, but not necessarily different. So, rhetorically speaking, why didn't Sylveon exist in Gen I, or Gen II at the latest? Why were Espeon and Umbreon, and Crobat and Blissey, and so on, so late?
If Game Freak wants to go and retcon many of the forms of evolution that exist at the start of each generation, I don't think I'd have much of a problem with it. It would just beg the question of "Why can Rhydon evolve this way now, when it couldn't before?". In fact, it might have been nice to see this in Gen IV with Gallade and Froslass, for example. Ralts, Kirlia, Gardevoir, and Chimecho were among the very last pokémon to be added to Gen III. This leads me to think that perhaps Gallade had been planned for Gen III as well, but they hadn't quite worked out the gender mechanics of evolution yet, or they had, but it wasn't important enough to focus on over other, more pressing issues. It would have been more interesting, I think, to let Kirlia and Snorunt have level based branched evolutions like Burmy, but instead they introduced the Dawn Stone - an item that hasn't been used for anything else since.
A lot of these pokemon don't need a full mega (and all that comes with it) to become viable. Even just simple stuff like gaining a new move or two can change a mon from useless to fantastic. Look at what happened to scizor between DP and Platinum -- it got a lot better just by having Bullet Punch added to its movepool.
Oh, I wasn't saying that they do. Viability isn't exactly what Game Freak si looking at when they create megas, anyway. Gardevoir in particular is a favorite of mine, and I've used her for years, irregardless of superior options, but the fairy-type alone was enough to give her a huge boost from Gen V. She didn't
need a mega, but I like that she got one. My point was that some pokémon would appreciate a mega because they've reached their potential in the current games, both in and out of the meta, while others
haven't, or have other options available to them
. At the moment, Haxorus might struggle in some areas or against other dragons, but if people like it, then they'll use it. It's the same concept that you applied to Scizor, just more dramatically implemented.