Back to the original question of bribing, it is "random" but not evenly distributed. As a general rule it seems there is about a 50% chance that the deed goes up in color, and then a 25% chance that it goes up in quality, 25% it goes up in quantity.
However, if you have a deed that is already, say, 20 normal iron, then there's a 75% chance it goes up in color, and 25% it goes up in quality.
Most people say "it almost always goes up in color", this is true, but that is mainly because there are more gains to be made in color.
With the fact that most rewards can be gotten a few ways, it's extremely unlikely for a deed to really go to waste. Especially in smithy, where you're nearly guaranteed that any iron armor deed will become either a shadow iron or copper hammer or a PoF - and with ingots that are pretty easy to come by.