Hearthstone is almost 2 years old. We have had 2 expansions and 3 PvE adventures. All of this has brought new legendary cards each time. Even if you have bad luck, and just did the adventures, you would have over a dozen legendary cards.
Scenes like this are all too common. In most matches, depending on the class being played, you can almost predict when certain legendaries will be played. You know for the most part, at 6 mana Thaurissan will come out. At 7, Dr. Boom is played. After that, it could be any number of legendaries on parade.
Now, I have to admit, a lot of times I am just as much to blame as the next player. I have my share of legendary minions as well, and I tote them in druid and warrior decks, among others. You used to get by being creative. Playing a mage with Mirror Entity, or putting a Faceless Manipulator in your deck was a way to even the odds.
When does it become overkill though? Just for grins, I decided to load up a deck and fill it with legendary minions. If I wanted to play this, I would probably take a few out and put some spells in there to make it really nasty. I seem to have 28 legendaries (not counting a few more class specific ones), and I can put them ALL in one deck. How crazy is that?