You are forgetting the other half of the top used pokemon. Gyarados does exactly two things: sweeps with dragon dance/waterfall/stone edge/ice fang or earthquake OR phazes with Rest/sleep talk/waterfall/roar
those are virtually the only sets gyarados used throughout all of 4th gen. Granted, you can play with his EV spread, but that hardly counts as versatile.
Then we have scizor, who nearly always runs a choice ban set with the same moves.
Swampert's list of frequently used moves is incredibly tiny too, as it is simply a bulky water stealth rock user.
Lucario, well, if you take a look at usage stats you will see that nobody uses specs. It uses a grand total of five moves.
That is all these pokemon NEED to do well. The number of pokemon with an obvious use balances out the diverse pokemon
I don't think I defined versatility well enough in my post, or at least as I was thinking of it at the time.
Gyarados can be tweaked to beat on defensive teams with that Taunt set, or go all-out LO sweeper. It does a fair job of countering other threats too, like Infernape, Heatran and Scizor. It also beats other Bulky waters without HP Electric, since Taunt prevents status and most other waters can't really hurt it back.
Right there I listed several different jobs one Pokemon can do with one set. it counters several Pokemon by setting up on them and thereby can really patch up a team. That's more versatile than, say, using Quagsire in Ubers to beat Kyogre, since Quagsire doesn't really do much else. A "Specialized" Pokemon as I was defining it is one that counters a very small group of Pokemon and is used as sort of a utility counter against those Pokemon. It doesn't see much use since it only really does that one thing.
Scizor was specialized, but still widely used simply because of the raw power of Dragon Dancers in OU and the fact that Scizor (being Steel) resisted Outrage. Once Salamence was removed, Scizor did drop in usage. I feel like Scizor's massive popularity was because it's job (Countering Dragon Dancers) was currently something that most players really needed done on their team. Then to counter that you had Magnezone, who is really a niche Pokemon. But in this metagame, that niche is incredibly relevant and useful, since many Pokemon are far harder to stop without Steels to resist their attacks. Scarftar also become popular in this way, as Latias became more powerful, and people wanted to stop it.
As the metagame shifts, some specialty Pokemon will become vastly popular because their specialty is currently needed to counter a dominant force in the metagame. If that force remains dominant, then the specialty Pokemon remains popular, like Scizor. But I wouldn't call Lucario a specialty Pokemon, since it does have those key resistances that allow it to patch up many holes on your team. Swampert does the same, although more defensively and without nearly as much offensive presence.
So I see what you're saying, I just don't think those Pokemon were "specialty". They still do a lot with a little when you really get break them down and look at them.
