Play prevention has always been part of the game... In the early days we had Muk and Dark Vileplume, in more recent times we had Manectric EX, Vileplume EX, Medicham EX, Houndoom (UF), Dragonite EX delta, Gardevoir EX delta, Cessation Crystal, Crystal Beach), LatiLock, Dusknoir (DP), Gardevoir SW, and I probably don't need to go into today's format. I can't think of a format in the past 5 years that I've been playing in which everything works... a format has always presented obstacles to any deck. It's just been poorly executed in the past 2 years.
I understand what you're saying in that Vileplume is never active, but unlike the list of cards I just mentioned... it's not a very viable attacker. Thus, most decks have to dedicate around 6 slots to a Vileplume line anyways just to make it work, and they still have to build their main attacker when they set up. Something like Gardy/Gallade and Mew/Manectric had their lock all set because their locking mechanism was attached to their attacking Pokemon.
A lot of those blockers had counters:
Dragonite Ex Detla - was never really good to begin with. So many people try to make it work since it was right after Mewtric won Worlds, but it just couldn't be "broken".
Houndoom (UF) - Cessation Crystal, Lati-lock or keep a small bench.
Medicham Ex - As you stated, it was an Ex so it had it's draw back of giving 2 prizes when KOed.
Cessation Crystal - Windstorm. But again was in a format that pretty much made you choose to either run Windstorm or a Cessation Crystal deck.
Dusknoir (D/P) - It's locking power didn't kill your opponent, it was kind of like Houndoom as it only restricted your opponent but within limits. It lost a lot of play once SP/P. Spray hit the scheme and stadiums weren't as big any more.
Then as you also mentioned G/G was just stupidly broken. Mewtric required a lot of skill to play, it was like the DialgaChomp of it's format. No random player could just make a list and go to tournament and expect to do well. It had few good matches, but few bad ones as well.
Locking is a part of this game, and a good one but as long as it's not broken. An example of this is Hariyama Ex locked your stadium and disrupted even more by discarding cards fro your hand, but it wasn't broken, it never really got into being a Tier 1 deck, but never lower than a lower Tier 2 deck. G/G was broken, Slowking was broken, Luxchomp is broken (it locks you from setting anything up as it removes your energy from play). I wasn't around in the beginning when Haymaker was around but I consider Luxchomp a faster, meaner Haymaker. It has the same tools, some even combined into one. Energy Removal/Gust of Wind into Luxray. As it's a good fast attacker being able to KO low HP Pokemon and remove your opponents energy from play.
Houndoom made you play with hardly any bench... >.> It came at a cost. Plus you could play Space Center or w/e it was called to shut off LatiLock.
And I would agree with you on Vileplume, but we still don't know what our next format is nor do we know what's in any upcoming sets. It's pointless to speculate how dominant Vileplume might be at the moment. PL-on, RR-on, SV-on, AR-on, and HGSS-on all create entirely different environments for Vileplume.
No one played that stadium, NO ONE. It was in the Cessation Crystal format, and like I mentioned before it was a format of almost none existent stadiums.
So far in spoiler for the next set for B/W sets we don't have anything else that shut off bodies. So it'll be until CC until we POSSIBLY might see something that does. Even if they do print something that shuts off bodies, we still have to worry about LostGar's dominance, :/.
Sorry if we go off topic with some of our discussions, but they do tie into the initial argument. We went from banning broken cards, to banning Vileplume, to how lock affects metagames,
broken cards affect Metagames is the core discussion of the thread. So please don't accuse us of trolling.