Now i DON'T want to make it another discussion about the meaning of randomness but if you want to narrow it down, and PLEASE understand don't get that wrong, the system I'd suggest has no "failures", so it it pretty close to Oblivions, BUT there is a FAR greater variance of the possible outcomes of which a lot COULD be considered a failure.
Let me try to explain with the lock picking, first of my idea is based on a total different system, not Oblivions "pin hopper" or morrowinds "click and watch" style, it still has player interaction though.
In that system you have to move the pins too but they are not visible to you, you can just hear and see when a pin is in it's "sweet spot" represented by a click and the lockpick "shaking" a little.
When your skill is fairly low your character still is quite a clumse so finding that sweet spot is hard, in game that's represented by the spot being very small so finding the right position isn't easy. Even when you do you still have to fix it in place so just finding it is no good, this could be done by finding the spot, holding the button till you hear another click meaning it's locked in place an doing that for every pin.
Now the difference is the locks complexity and your skill, a complex lock will have more pins (maybe like a bank vaults key that even is double sided) and they are much more fine tuned so the sweet spot is harder to find. A very simple lock might only have 3 pins and it's made quite roughly so it's not even that hard to crack for a newbie. This means you not only have to place more pins correctly on a complex lock but the mechanics are also finer so the exact spot for the lockpick is harder to find.
The skill has the same influence, the higher your skill is the bigger that spot becomes since your character can feel it better, kinda like when trying to read braille at first you just feel "some dots" and with training can identify their position better.
However now you say "just give it enough time and you can crack any lock", not exactly. When on very low skill the exact point is pretty much nonexistent so a lock that's far to complex is nearly impossible to open. Then some locks might require special toos to open so you can't do it with a normal lockpick. Also in the time it takes you can get caught (no time freeze on lockpicking). Trying to pick a lock while very unskilled is also noisy and leaves marks on the lock so someone can be attracted by the clicky and crackly noises (specially house owners who's front door you try to open) and people can notice someone tried to/did mess with the lock and be alert, so even when you're in the house already people can be aware of it and search you. So low skill = you're more of an attention magnet == not good for a lock picker.
However your skill also has one influence, your character can "keep cool" longer. The longer you try to pick a lock the more nervous your character gets which again results in the pick spot for every pin shrinking making it harder. Even worse when your character runs out of stamina it can happen that he drops the already picked pins again making all progress useless = effectively failed.
This would make skill progression important to crack more complexe locks, you wan't be able to crack the banks vault at low level but even at high level it won't be childs play.
Well this got kinda long.
Hmm well i guess i could say this, if you submit something maybe say how you imagine a certain aspect to work since, with the lockpick example, the mentioned base systms are very different.