In a deck built around flooding the board with minions, I've noticed Hunters tend to be by far the largest issue, because in addition to having access to easy and cheap board clear, they also have unleash the hounds, one of the most insane 2 drops in the game. I personally have two decks, paladin and shaman, that are built around having a large number of small minions on the field.
Firstly a word of advice based on your commented deck list. If your do really enjoy flooding the board using your power, I would highly recommend you consider cutting down some on your four drops and increasing your number of three drops and maybe even two drops. The advantage of this is that, it makes you more likely to be able to use all your mana in a turn for maximum efficiency. For Instance:
- Turn 2: Use Power or play relevant 2 drop, depending on board state and opponent power.
- Turn 3: Play 3 drop
- Turn 4: Use Power and play relevant 2 drop, OR play 4 drop.
- Turn 5: Use Power and play relevant 3 drop.
Alright, regarding your specific issues against hunters, one of the best counters to unleash the hounds is high toughness taunt creatures, or having a number of taunt creatures. The big issue is that most hunter decks will be running 2 silence owls, so oftentimes they'll simply silence your large taunt creature, and then attack past it. Some possibilities to fill this role include:
Sen'jin Shieldmasta: Hands down one of the best taunt minions in the game, Sen'jin can usually eat up anywhere from 3-5 hounds from unleash the hounds, depending on how much support your opponent has for the unleash. In addition, Sen'jin is relevant against a large number of other decks unlike some other large taunt creatures. I would definitely consider running 2 of these if you tend to have issues against aggro decks. The big downside of him against hunter decks, as is the case with most bigger creatures, is he dies to a kill command.
Tirion Fordring: A very powerful legendary creature, if you have him, I would highly recommend running him, as he's hard to kill and still impactful upon dying. The big issue with him is that he is one of the biggest blowouts if he's silenced, just becoming a measly 6/6 for 8 if he is.
Abomination: Abomination is, in my opinion, a very underrated minion. He is amazing against Unleash the Hounds specifically, almost always clearing all the hounds on his own, in addition to any potential support your opponent might play, such as timber wolf and starving buzzard. The big downside of him for you is that he basically acts like an exploding trap, most likely killing all your token minions.
Defender of Argus: Defender of Argus is an amazing creature, especially for a paladin, who is easily capable of making sure he has the creatures to use it with. The big downside of him in this case is that if your opponent has Timber Wolf, their hounds will just trade for your 2/2 soldiers. I would still recommend at least running one of him in your deck, if not two, because there are many times that he is relevant.
Sunwalker: One of the hardest to straight out kill taunt creatures, sunwalker can be very impactful upon the board. The big downside of him is that he's highly susceptible to silencing, and is somewhat high costing, especially if he gets silenced.
Fen Creeper: Generally considered to just be a worse version of Sen'jin, he is still not a bad consideration to put in to the deck if you're having that much difficulty against hunters. The benefit that Fen Creeper has over Sen'jin is that he won't die to a single kill command, taking both a kill command and a hound to kill, and still eating up between 3 and 6 hounds if they don't have kill command.
Sunfury Protector: A tiny version of Defender of Argus, I would be hesitant to run this in your deck, since you're most likely going to have only small minions to use her with. Still, her ability can be very relevant, as she'll force your opponent to clear two of your minions before they can attack you.
Mogu'shan Warden: As a last ditch effort, if Unleash the Hounds is absolutely the bane of your deck, I would run Mogu'shan. He is often very irrelevant against opponents, but against Unleash the Hounds specifically, he is one of the best minions out there. Again though, he's not very good against most other decks.
Worrying about clearing the board of an unleash the hounds after their turn is less of a big deal, as you should probably be saving your consecrations for just such an occasion if possible. If that is a concern though, you can also add Avenging Wrath to your deck, as it's an excellent board clear against Unleash the Hounds, and in general, is just a rather good spell, at worst being 8 damage to the opposing hero for 6 mana.
Regarding the other aspects of the hunter, having big taunt creatures also helps to avoid your creatures' divine shields from being removed, by protecting the smaller divine shielded minions. In addition, divine shielding a Sen'jin Shieldmaster or Abomination can be pretty powerful.
In respect to the explosive trap, unfortunately, there's not many counters to it in a paladin deck besides playing around it, or using divine shields. If you're truly worried about it, consider doing little other than using your power until your opponent uses their first explosive trap. If you bait out an explosive trap, you can much more confidently attempt to establish board control by playing a number of cards from your hand after it explodes. Divine shields though do suffer from the issue of being easy to trade a small minion in to remove it. It is why I would probably not run Hand of Protection, but would definitely still run Argent Protector, as a 2/2 with 'Give a friendly minion divine shield' is pretty good.
Scenario 1:
In most cases, mulligan for your combo!
Since your deck has no Wild Pyromancer and very few early drops, I believe your best chance for taking control of the field is your Auchenai Soulpriest and Circle of Healing combination.
Grabbing control of the board against aggressive decks is key to winning when playing as the Control Priest. Therefore, this combination is so important, that you should mulligan aggressively for it.
That said, if you have a 1 and 2-drop (Northshire Cleric and Acidic Swamp Ooze) or a 2 and 3-drop in your hand in addition to the Circle of Healing, playing those will give you enough board presence early on to protect your health until you do draw your Soulpriest (or at least have enough chance to draw it as you would with a mulligan).
Scenario 2:
Mulligan Thoughtsteal. Below is an explanation why.
I am assuming that Dark Cultist or Injured Blademaster is a better turn three play than Thoughtsteal in most circumstances, so you would rather have one of those in your hand. Since you have two of each Thoughtsteal, Injured Blademaster, and Dark Cultist, you have six cards that you could draw by turn three that would be as good or better than Thoughtsteal.
- Mulligan
- You keep 2 cards and mulligan Thoughtsteal.
- There are 5 cards as good or better in your deck.
- Your deck has 27 cards.
- Chance that you draw something worse for turn three: 22 / 27
- First turn
- You drew something worse.
- You have three cards in your hand and you draw one.
- There are 6 cards as good or better in your deck.
- Your deck has 27 cards.
- Chance that you draw something worse for turn three: 21 / 27
- Second turn
- You drew something worse.
- You draw another card out of your remaining 26 cards.
- There are 6 cards as good or better in your deck.
- Chance that you draw something worse for turn three: 20 / 26
- Third turn
- You drew something worse.
- You draw another card out of your remaining 25 cards.
- There are 6 cards as good or better in your deck.
- Chance that you draw something worse for turn three: 19 / 25
The chances of all of this happening in sequence is (22/27) * (21/27) * (20/26) * (19/25) = 37%
That means you have a 63% chance to draw a replacement Thoughtsteal or one of your Dark Cultists or Injured Blademasters by your third turn. Therefore, mulligan that Thoughtsteal!
Remember, in a control match-up, you have a very good chance to draw it again later, when it is more useful.
Best Answer
If you take a look at how popular players/deck creators work, it's a combination of intuition about deck synergies and a trial and error process that progress through subsequent refinements.
Take for example Anyfin Can Happen: it's clearly designed to belong in a combo deck, with its high cost and high board impact. So you start from this idea and try to build the deck around it.
One of the first thing you have to ask is: "What is my win condition?"; what is the mechanism that gives you victory? It can be a specific combo or even just a simple "get board control and smash the opponent's face". Usually you try to get a win condition that fits the class you're building: if you try to make a Shaman fatigue deck, you're going to have a hard time, while for a Warrior deck it may be more manageable. Figuring out a good/original win condition is usually one of the hardest parts of creating a new deck, and requires a good dose of skill, creativity and understanding of the current metagame: this is because you have to clearly have in mind how the class you chose works and you should also know how the cards in that class work.
Once you have a clear win condition you have to ask yourself: "How can I achieve that?" Here comes the trial and error part: now you'll have to actually build your deck and test it through dozens of matches to verify that the synergies you're putting in actually work. Take for example the aforementioned Anyfin Can Happen: once you put that card as your win condition, you set your deck on a path that requires card draw (or else you risk not finding the card), self heal (you have to survive until turn 10, or later), board clears (to avoid being overwhelmed by the opponent's board) and the right amount of murlocs in your deck (a board full of Murloc raiders on turn 10 is going to be useless).
The first iterations of Anyfin paladin were clunky because were including too many murlocs or were lacking good ways to clear the board. Once people started including Doomsayers, Pyro+Equality, Lay on hands, and, most importantly, reduced the murloc presence to just Bluegills, Warleaders and Old Murk-Eye, the deck finally found its definitive (and fearsome) incarnation.
Naturally this is just an example, but the thought process usually is similar. It takes creativity to come out with a new deck archetype, but it also takes a lot of work to make it actually ladder-viable.
One final note: if in 75% of the cases you lock your hand with dead cards you may have to reevaluate both your deckbuilding process AND your game plan. The whole deck needs to progress your match towards your win condition, but also it's important the way you play it. The mulligan at the beginning may be the difference between a glorious victory and a catastrophic loss. You can't keep in your hand the same cards against an Aggro Shaman or a Control Warrior, but the only way to become good at this is actually knowing what you're facing. You have to understand the meta, calculate the chances that the player you're facing is, for example, a Face or a Midrange Hunter and change your game plan accordingly.
Since you mentioned creating reliable decks let me give you another advice: don't craft or disenchant any card until the new expansion becomes available. Whispers of the Old Gods, as you probably already know, is going to introduce new cards, while restricting many others to the Wild game mode only. The meta will shift a lot and decks considered solid or at least playable today may not be viable at all when the patch hits on April 26th (27th for Europe and Asia). If you have the cards already available, play with them, otherwise don't craft any new one for the moment. If you want to "have a good start", wait. New strong decks are going to rise, creating one today will not help you in a week.