Montresor does not use his trowel to search the recess where he has imprisoned Fortunato. Here is the passage in question:
A succession of loud and shrill screams, bursting suddenly from the throat of the chained form, seemed to thrust me violently back. For a brief moment I hesitated -- I trembled. Unsheathing my rapier, I began to grope with it about the recess; but the thought of an instant reassured me. I placed my hand upon the solid fabric of the catacombs , and felt satisfied. I reapproached the wall. I replied to the yells of him who clamoured. I reechoed -- I aided -- I surpassed them in volume and in strength. I did this, and the clamourer grew still.
Poe specifies that Fortunato is wearing a tight-fitting jester's costume. He would be unarmed. Montresor is wearing a short black cloak and has a rapier concealed under it. He has Fortunato at his mercy from the time they enter the underground vaults. He could kill him with his rapier any time he wants, but he prefers to kill him in the manner he finally does, which may explain why he acts in such a zany fashion. He is momentarily alarmed when Fortunato begins screaming, and he thinks of stabbing him to death. But then he realizes that no one could hear his victim no matter how loud he screamed. Poe wants to show the reader that the plot is foolproof. Montresor can carry out his revenge with the "impunity" which is so essential. He can leave Fortunato there behind the wall and his victim can scream his head off without being heard. In fact, Montresor would probably like to think of Fortunato screaming and screaming in the dark until he finally gave up hope.
This is where he had stashed the bricks and mortar ahead of time to wall up Fortunato within in the Montressor catycombs. Montressor's act was premeditated as he had prepared in detail beforehand all he would need to finish Fortunato off once he had lured him into the catycomb.
His plan seems to have worked since fifty years later nobody has disturbed the site save for Montressor himself and whomever he is talking to. Makes you wonder if the listener (reader in this case) is to be the next victim....