I had tons of funs playing Priest since Core was introduced, but it always felt to me like flipping a coin. Got matched up against Warlock? You best concede. Playing against hunter or paladin? He should be the one who concedes.
In general the decks I came up with before the miniset were very polarized, ranging from 5% WR to 95% depending on the opponent.
This deck, however, is more consistent! You won't be able to counter every single one of your nemesis' games, but your chances increases greatly, without impacting the global WR against other classes.
I got to Legend with 20W 6L so 77% WR.
Strategy is simple, however the execution is a bit tricky.
Vs Hunter and shaman, mulligan for your early removals. You have a high WR against them, I'm at 13-1.
Vs DH, against either otk or deathrattle, you will need to find your disruption cards. Vol'jin and Mutanus are key to winning. I got to 5-2.
In control heavy matchups (warrior, priest) is where the mill part begins.
I like to stock up on Prize Vendors and Southsea Scoundrels, keeping the opponent under the illusion that we are just a control deck. Then, on the turn they let their guard down with 8 to 9 cards in hand, we go all in. Southsea Scoundrel should always be played last if you can mill a card as you get to discover a great card to draw that the opponent will burn. Mwahahah
Meanwhile manage your own hand size as Southsea Scoundrel is a common card in control decks, your opponent might have their own.
On those control matchups it is best if possible to avoid playing bad minions like Blademaster Samuro or Lightshower Elemental. You want Raise Dead to bring back Southsea Scoundrel, Prize Vendor, Mutanus the Devourer, Venomous Scorpid
Over the length of one game you might only mill 1 to 3 cards, but I won games that were really unfavored to me, burning chtun parts, Il'gynoth, etc.
Have fun :)