Thanks for your comments, everyone! Sorry, I was on holiday, but I'll try to answer to some of your points:
You mentioned how you didn't know much about the meta pre Heart Gold / Soul Silver. There's a wordpress site that actually discusses main decks from the original base set in 1999 all the way to Black and White. It's called Retro Pokémon TCG - History, decks and strategies for formats from 1999 to 2013, written by 3-time World Champion Jason Klaczynski.
I know about that site! I've read it, although it's been some time, so I may have missed recent articles. It's definitely a good read.
I have to disagree, especially since the provided example hasn't really proven this point. Active abilities like Zoroark-GX or Gardevoir-GX make the deck harder to pilot and learn, but their effect on the actual strategy of the game is sparse. I had a full Gardevoir-GX deck - I wouldn't rate its complexity as too high, but most importantly it wasn't that strategic to play with.
I would compare Pokemon more to chess than any other TCG. In chess, your main skill comes from seeing an unraveling chain of events after every move. This comes from analyzing every possible move of your opponent. Tense situations usually result in a series of takes (OHKOs, anyone?) that end up with a slight advantage for one of the players. That skill increases with more active pieces there are on the board. If each meta deck has two offensive Pokemon with predictable attacks, it's extremely easy to predict the chain of events that'll conclude five turns from now.
The two things that, in my opinion, really increase the strategy, are: the multiplicity of possible attacks on Pokemon and high deck flexibility. The former shows when you have a bunch of loaded-up Pokemon with different attacks and also different types and weaknesses. If you know your opponent has multiple answers to your next attack, you must predict that chain of events for every option, and the skill increases.
The latter deals with deck predictability. If your deck is extremely tightly packed to be competitively consistent, then I can predict every tech card and even read the contents of your hand. Pokemon isn't really a game of bluff like Magic, but if your deck has a lot of varied tech and multiple tech cards can apply to a single situation, then see above: complexity and difficulty of predicting the future increases.
I believe the main culprits for why playing VMAX/Tag Team decks are simplistic are - the damage/health disparity means that suboptimal attacks become really suboptimal. When Sun & Moon came out, I remember Alolan Vulpix being played for its free attack to find any two Pokemon, even without any Ninetales. Nowadays, this card wouldn't even lay next to a VMAX deck. Even if you're playing Cinccino, you're not going to use their attack unless in extremely edge cases. I remember playing Glaceon-GX and attacking with Alolan Sandslashes - their attacks were bad, but they weren't "40 damage to a 340HP beast" bad. Effects like Poison and Burn are basically null right now. Secondly, these VMAX decks are relatively tight - partially because there's so many autoincludes printed.
And finally, Counter Catchers without Guzma in the format were unironically great. Each deck has two Gusts at max, they had to work the deck to get it, and they might even choose to sacrifice one through a discard. If only they appeared in an otherwise healthy format, I think players would be thankful for how much more strategic the game is when your opponent can't choose what they'll attack each turn.
I agree that the multiplicity of possible attacks is a factor that makes decks (or a format, if taken globally) more interesting to play and to play against. It's a good point and one I wish I had explicited as clearly as you did. I don't think it's the only factor, though: using an attack is obviously an important part of the turn, but it's not the only part where you make a part. The choice of which Supporter to play, for example, can also be very important, especially in decks that have draw engines and can afford to play more utility Supporters. For example, choosing whether to play Judge, Acerola or Guzma on a given turn when playing Zoroark can be decisive.
As for Gardevoir GX, it was played differently depending on which format, but at Worlds 2017 the deck played a secondary attacker in Gallade BKT (whose Ability also led to interesting decisions), fall 2017 it was often played with Sylveon GX so you had to choose when to use Magical Ribbon and when to attack, and the option of Plea GX was also something to keep in mind. In SUM-LOT the deck could also attack with Solgaleo GX and Swampert. And of course there's always the decision of when to use Twilight GX. It's true that you'll use Infinite Force most of the time, but I don't think that's enough to be able to predict how a game will go. (Again, there are Supporters like Acerola, cards like Max Potion, etc., that also play a big part in all this.)
I agree strongly with "suboptimal attacks become really suboptimal". Some Pokémon are made to be competitively viable (mostly, but not only, V, VMAX, Tag Teams, etc.) and the rest are kind of abandoned. I actually enjoy limited formats (draft and even prereleases, although that has its own issues), in part because there isn't this huge disparity.
After reading the article, there is much I agree with, with one part questionable.
The questionable part would be Seismitoad-EX being an overall good, which I found the total opposite. The problem was if the card meant to slow the rapid-fast decks, it did a miserable job at it: It instead made the meta it was in even faster in order to actually counter it. In other words, it made Night March and other decks do all in its power to outmuscle the Toad before it could just dumbly throw quaking punches and laserbanks to lock opponents from the game. I despised Boundaries Crossed - Roaring Skies before the Lysandre's Trump Card ban because Toad strategies were so Poisonous, even the Virizion/Genesects would lose to it. People had to do other weird decks, like Blockade Exeggutor, just to beat the Toad.
If anything, the ones that really slowed down the game at the time were Wobbuffet and Waiload-EX. The introduction of these two were really helpful, in that they helped prevent the speed decks from going out of control, and actually made slower decks worth using. Primal Groudon, a fairly costly card to control, became a great card with an Ability blocker slowing the Shaymin-EX centric draw engines - and it allowed slower hit and run decks to exist for a time. And the actual introduction of 'stall' made sure resource-splurging decks would get punished if they weren't careful.
Seismitoad-EX is definitely very polarising. I'll confess that I liked playing Toad/Slurpuff in the BCR-PRC format because of completely broken it was, but I know many people complained about that aspect of the format and I agree with them.
I stand by my point, though. Toad was a good addition overall at the time and made the game more interesting than most of what we had the previous season. It did create issues as time went on (Shaymin EX made it even more ridiculous, and not as fun to play imo), but at the time of its release, it was good to have it in the format. I also don't think that Night March, for example, would have played slower without Toad.
I like Wobbuffet and I agree that it's a healthy card. As for Wailord EX... it was never intended to be played the way it was, so it's hard to compare. Stall did introduce a new aspect to the game, which was interesting at times (and did affect the way people built their decks), although often frustrating to play against. But it was never planned by the game designers.
For me, I'd like to see an alternate format consisting of only Common-Rare (Yes Rare, not Rare Holo) Pokemon cards. While that could potentially bring in it's own fair share of delinquent cards, it would eliminate a chunk of the big basic format. I grew bored of this game because almost everything has to be big and hit hard half the time. In my personal opinion, it got boring, stale. All I ever really want the cards for now is the artwork, and having a big obnoxious recycled 3D model as my ultra rare makes me lose even more of my interest. The last time I ever felt I truly had a ton of fun with this card game was indeed the HG/SS - Noble Victories format.
I'd like to play this game in a format that gives more than just the big basic/triple prize Pokemon the spotlight.
That would be very interesting to try. It might be necessary to have a ban list to avoid something like mill or control being far too good, but actually maybe in a slower format, decks could be built in a way to beat these decks.