The issue with setting guide lines depends on the regidity of the game itself. In rules light games translating believebility into numbers is usually simpler because the modifier scale is not as granular. In a game where a +/- 1 is important and +/-3 is extremely rare then assigning a challenge/complication is easier. You really only have to look at how much of an impact it has on the story and go from there.
In D20 or any other game that works with a more granular difficulty scale it becomes a little harder. Personally I'd try and keep it in incriments of +/-5 that is appropriate for a D20 based scale. With that in mind it should be just as easy to decide on how much of an impact a particular challenge/complication will have. As for actually trying to give some examples I'd have to pour through some other games that use this sort of mentality to try and come up with a scale. But it should be relatively easy to create a universale type of scale that could be used in any game, you just need to modify the numbers to the mechanics.
But this mechanic removes one of the possibilities in my original idea. It's the "success despite task failure" that isn't represented. Not a big deal, perhaps, but I want to keep at this. There should be a way to represent all the possible outcomes somehow.
I was thinking about your succeeding despite failing at the task and how to turn that into a mechanic. You could work that a few ways. The easiest way would be through the use of a luck/fate/action point system. You spend a point and can then narrate your success of the goal despite your failure. This would limit the number of times you can do this and a mechanic like this would feel pretty comfortable in a more chunky game system (D20, Warhammer, Paladium etc...). It's also a pretty simple/quick way to do it.
An example, is you fail your task, spend your 'point' and you have now simply succeeded. This style of mechanic is kinda boaring, but it'll work.
The other way is to apply complications after fact. This style would be total narrative control and need to collaborate between player(s) and GM. The player would have to accept complication(s) to offset his failure enough to equate success at the goal. Think I'll need an example here.
Our friend the theif is sneaking past the guards and fails his sneak roll. However he doesn't feel like batteling the guards. So he (the player) takes control he must now introduce a compilcation to be able to achieve his goal of getting past the guards. So he says that as he's sneaking by he bumps a table knocking a vase to the ground. He quickly tries to throw his hat under the vase to cuishon the fall, but fails. The guards come running in as but he manages to duck around the corner.
So he's gotten past the guards - however his life has become more complicated now because the guards see the vase on a hat and now know somone is there.
Another exmaple would be the maid one. He fails his sneak so he takes control. He narrates that he did infact sneak past the guards but then bumped into the kitchen maid so now he has a new goal get past maid. So his taks is probably a (bribe/bluff/intimidate) check which could accpet more challenges/complications to get out of this new situation.