Two things I hate about modern RPGs: Everything revolves around combat and non-combat interactivity-- everything from crafting to searching to lockpicking-- rarely involves any real risk.
So what about this: Tie skill tests to a gambling mechanic that impacts character advancement. It's not a new idea as tabletop games have this, but I think they usually apply to special tasks, like item creation or bonus die rolls in tough situations. I'm thinking more along the lines of a character point system for developing a party, with points rewarded for success and taken for failure and with the ability to wager points for critical success/failure.
I can only see this working if there are many things to buy, several characters to spend on and the costs for higher tier character development scale (exponentially, probably). It might also be necessary for spamming to be controlled by risking risk and stable reward, so that if you want to search 300 times in an area maybe you're only gaining 1 point but increasingly risking more and more in a sort of "house always wins" mentality over the long run.