Hearthpwn

this is the deck that I used for Heroic Arch-Thief Rafaam. there are 2 or 3 things going on with this deck. the 1st is to give him cards  with bad stats or abilities (wisps, ancient watchers, eerie statues, etc) and when possible, 2nd to make them Rares so as to buff Rare Spear.  I didn't want to go all-in on this however, as I often don't draw the spear until late, if at all. half the deck being rare seems like plenty. Finally, the 3rd aspect of this deck is to give him cards that draw cards and fill his hand so that he doesn't get something good off his hero power. adding Baron Rivendare and another Loot Hoarder might be a possibility to aid in this, perhaps replacing the 2 Divine Favors (though at worst these just become dead cards late game that help fill his hand because he can't play them, which functions somewhat equivalently to making him draw; and if he does get the opportunity to cast it early, it serves as a buff for the Rare Spear as well). Coliseum Manager is another card I didn't think about but would work great.

the draw cards are the only paladin cards in the deck, but the hero power gives you a target for Explorer's Hat and lets you trade with the weenie minions in his deck.