Yeah, it really does. An unparalysed Alakazam will tear through any physical 'mon that tries to attack it, while being almost impossible to break on the special side due to Recover backed by insane Special and Speed stats and a total lack of weaknesses.Alakazam is not a staple, and is replaceable on almost every team (I mean, Alakazam doesn't change too much the metagame without its existence).
Alakazam is what makes it necessary to play methodically in RBY rather than just going for an all-out offense, because anything trying to get past an unparalysed Zam is going to end up paralysed if not outright destroyed - and Zam isn't even badly inconvenienced by the damage, because it can just use Recover before your next 'mon gets to move.
You can run Exeggutor without Sleep Powder or Explosion and it's still a ridiculously good 'mon because of its awesome stats and typing. But it will always need Psychic.Exeggutor is the only one that is a staple and need Psychic to be usefull. But I found out that when I play with it, 3 out of 5 battles I don't even use it. Still, Sleep Powder and Explosion are better moves than Psychic.