More on topic, I think I would rather have the mini-games work in conjunction with skill checks rather than as a replacement for skill checks.
For searching, say you have twenty locations to search to find one item. An Easy Perception check allows you to search one location, a Moderate Perception check allows you to search two locations, and a Hard Perception check allows you to search three locations. The player gets involved because he has to pick which locations to search after a successful Perception check, and if you add a time limit (traps going off, battle going on, roof collapsing, guards arriving in a few rounds, etc.) you also add a tactical dimension to the game: go slow and steady with Easy checks, or risk a Hard check?
For picking a lock, perhaps the players have to obtain a specific combination of 20 numbers. A Moderate Thievery check reveals one number, and a Hard Thievery check reveals two. The player of a character who fails the check can still try to detect the underlying pattern and make a guess. You can use the same time constraint factors mentioned above to add a tactical dimension to the game and give players an incentive to guess even if the Thievery check is failed.