You conveniently fail to mention the flip side of thoughtsteal, it can steal game breaking class cards that Priest is not supposed to get a hold of. Overall, thoughtsteal draws you two good cards, since in constructed no one runs trash cards and only a very small pool of neutrals get used, with a decent chance of drawing you a class card (possibly game breaking), and a very small chance of drawing you a specific combo card (outside of your example, these are not common). Blade fury, deadly poison, and shield slam are about the only dead draws in the current meta. A rogue will only run one blade fury in general, and two deadly poisons, giving you a 10% chance for a dead draw against miracle (an already bad match up for a priest), but every other card aside from Southsea Deckhand is either useful or great. Against warrior, a brawl, Grom, Alextrasza, Ragnaros, or Sylvanas will probably seal a win for you unless you screw it up. Even something as simple as a weapon is ridiculous value for a priest as he has a number of tools at his disposal to counteract a weapon's only downside.
In addition, since the cards aren't taken from your deck thoughtsteal also increases the total number of cards you can use throughout the game by two, which is a significant advantage for a class that often aims to bring its opponent to fatigue. One of the worst parts about this card, though, is that the opponent has little way to predict which card was stolen. Half of the battle is knowing what your opponent can play by the tools his class has at its disposal, and being able to use this knowledge to plan ahead. This card significantly mitigates your ability to do that.
I am not claiming that Thoughtsteal is overpowered, but it absolutely can allow a Priest to win a game through RNG. Yes, I am still butthurt that a priest stole equality and what I am sure was my Harrison Jones when he had nothing on the board with 10 health left while I had Tyrion, Kel'thuzad, and a guardian out. I suspect that as classes become more distinct, and the neutral pool expands, thoughtsteal will cease to be usable.
As for your points on the undertaker, and t1/2 victories, I must also disagree. To be clear, obviously no game is decided until one player is dead, but with some opening hands, your hope of survival are so vanishingly small that it is probably a more efficient use of your time to concede. Yes, they can be stopped dead by early removal and Sludge Belcher, but most classes simply don't have the ability to deal with it efficiently, and stopping the undertaker isn't enough. The only early removal for a strong undertaker rogues have are backstab+something else or something else+eviscerate, druids have wrath or keeper, mages have frostbolt, hunters have essentially nothing that deals with a 2/3 except for traps or a stronger undertaker, warriors have fiery war axe or execute, warlocks have soulfire and mortal coil, priests have shadow word: pain, shamans have lightning storm/lightning bolt/rockbiter weapon/earth shock/wolves, and and paladins have the concede button. Of those, only the warrior, druid, and shaman have an efficient or consistent way of dealing with this one drop, but they still have to deal with everything else being played. It is not as if, ignoring their synergy with the undertaker, deathrattle cards are useless. In fact they are some of the highest value cards in their mana bracket. Even if you manage to deal with a strong hand, you still rely on passive defenses to control the board. Sludge Belcher is good, but if you have spent all your time removing their threats, then there is a reasonable chance that you have left them with a silence in hand. Once they have dealt enough damage to you, hunters can entirely circumvent the board due to their incredible damage reach, and warlocks can finish your passive defenses with a good soulfire/power overwhelming/doomguard which thanks to their hero power, they have a very good chance of drawing.
If you can't deal with the undertaker, then you have almost certainly lost, but even if you can deal with him, he has still in all likelihood put you behind. He is too good for a one drop, but maybe GvG will reduce his prominence so that we can see more diversity in the ladder.