Decks like Tez or TPS rely on the mechanic of tutoring (Demonic/Vampiric/Mystical Tutor, Tez, Tinker, others). I think it would be interesting to print cards that specifically hate on this mechanic, more so than Aven Mindcensor does.
Soul Scourge Trap

Instant -- Trap
If an opponent cast a spell and searched his or her library this turn, you may pay

rather than pay Soul Scourge Trap's mana cost.
Search target opponent's hand and library and exile one card from each. The opponent shuffles his or her library. Draw a card.
Exiling from both hand and library ensures that you nail both Demonic Tutor and Vampiric/Mystical Tutor. The "cast a spell" clause is to mitigate the usability of the card against fetchlands.
To the best of my knowledge, this won't actually foil Demonic Tutor due to the active player having priority during his or her main phase; they can play the tutor, pass priority (you can't play your Trap since they haven't searched yet), then tutor resolves and the stack empties. After the resolution they have priority once more as the active player and can cast the spell they tutored for before you have the chance to respond with your Trap; by the time you can finally cast your Trap, the spell is out of their hand and onto the stack. (If I'm wrong about how this works, let me apologize in advance; I am not an authority on passing priority).
With that said, this looks like a very good card nonetheless. In fact, I almost wonder if it might be
too good in Legacy as just a hand disruption plus cantrip for

, ignoring the cap effect. You could play it main deck in multiples since almost every non-Dredge deck uses fetches and is going to cast spells every turn for the first the first 5 turns or so. I think "cast a spell" should read "played an instant or sorcery."