I was watching a popular Hearthstone streamer, he was playing constructed versus his Warrior friend. They have played few games, and almost every time streamer's rush was countered by early Fiery War Axe. (he was whining a lot about this)
What is the chance to have one of Fiery War Axes by 3rd turn?
Let's say opponent goes second, meaning he gets 4 cards. Fiery War Axe is high priority card, meaning he will probably keep it if he got one, and replace other cards in hope to find one. By turn 3 opponent have 23 cards left in his deck, 2 axes. This is solid chance to actually have one, given he had opportunity to replace up to 4 starting hand cards, which is almost as good as having 4 additional draws (more elaborate description of starting hand replacements mechanics).
I think it's fair to say opponent will replace at least 2 cards from his starting hand. So our final calculations are approximately this: 21 card left in deck, 2 threats. Then it's fair to say that this will happen in about every second game. Which means if your opponent have early Fiery War Axe - this it not some kind of insane luck. This is pretty common thing to happen.