Hearthpwn

In this expansion, there is a clear path:

Step 1: Play Nzoth late game, then the Priest will spent his turn to clear board

Step 2: the board is empty now. Alex his face

Step 3: The Priest has to do 2 thing now in order not to lose: Kill Alex, and put enough minions on board which total hp+ his health > 30. If he fails to do this, C'Thun and you win.

As someone playing mainly Raza priest lately, I must say that the only times I usually lose to warrior are against odd Silas otk warrior. One time I even managed to burn the Warrior's Silas with my Mindrender Illucia, but he still won. I don't have enough games against Bomb Warrior to say too much about it, but the shuffle mechanic can be a good counter to Polkelt in addition to the obvious effect of countering the highlander cards. Most Raza priest games seem to be won by chipping away slowly or stalling until they can perform their 26+ damage combo. If you can get enough armor, then the priest might have difficulties performing his combo without killing himself in the process. 

Pretty impossible in Standard, Wild is a different story. (i know this isn't the answer you were looking for, but ..

hopes aren't high of winning against Priest)