I've only been OTK'ed by a Patron Warrior a few times out of the hundreds I've played against. Just look at your end line: "They pull all of their good cards". No. They don't. They often have shit in their hand and if you can force them to start using cards against your opening 5 turns worth of minions/weapons/whatever, you can draw them into a losing game. If they're drawing insanely and have multiple Acolytes out or some other such, hit the acolytes to force them to overdraw. Overdrawing even one card can destroy a Patron deck easily, as you should have noticed, their entire deck revolves around milling cards to get what they need. Loatheb, forced overdraw, early aggression, taunt minions and more can draw them into a prolonged battle or cause them to straight up lose.
I've beaten many, many, of them with Mid-Range Paladin, Control Paladin, Face Paladin, Face Hunter, Mid-Range Demon Warlock and a few other decks. They're not imba, they're not invincible. OTK decks have existed forever and are nothing new.