Never seen the No Removal Gym actually. Looks interesting, I would have hated that back in the day. (I played slowpoke removal)
Anyway, every TCG has a couple of cards that are good enough to run in every deck.
YuGiOh is a prime example. Mirror Force, Mystical Space Typhoon and Heavy Storm have been around since forever and are still some of the best cards in YuGiOh. They're versatile and pretty much good for every strategy. Energy Removal is one of those as well.
Catcher...maybe. It is good, yes, but it's not an auto-include in some decks. If they reprinted Energy Removal, I'd pick that over Catcher any day.
Also, an opening hand with 4 Catcher is horrifying. An opening hand with 4 Energy Removal is excellent.
Anti Catcher Stadium would mean you use your own 4 cards to shut down 4 of your opponent's cards. A direct counter like that is never good since you're playing the passive game in a TCG filled with beatdown decks. Also, they're dead if your opponent doesn't draw Catchers. The better option is to just get 4 Catchers yourself and if you get Caught during a game, deal with it. If pretty much every good deck plays it, it's not a big deal anymore. Just like Mystical Space Typhoon.
On a side note, discarding 2 cards was pretty small back in the day. You're discarding for Professor Oaks anyway, so it's not a big deal. Nowadays, I'd still gladly discard 2 cards (sup Junk Arm) to get myself a good old Energy Removal, even though the draw is a bit slower this format.