What I think happens here is that , as Rutra says, the shadow is set to "shadow map-raytraced hard shadow", guess you are using a spotlight here. If you then add softness to the shadows from the object properties panel ( preview sphere, upper right corner), you can actually lose the shadow completely.
So for soft shadows, I would recommend:
Using "shadow map-soft shadows", but the results may nopt be accurate for a spotlight, you'll need a fairly big map to get pleasing results ( check the auto size button, and limit the max size to 2048, if you go higher, there's no point using a map). This works well for a point light, should not be used for the sun
Or raytraced shadows with 5% softness added from the object properties panel. This will give you 100% accurate shadows, with physically correct blurring on the edges of the shadows the further away the shadow is from the lightsource, at the expense of longer render times.
Or for a spotlight, shadow map-raytraced hard shadow, without any softness.
As for 100% shadows, I rarely leave it at that, I go for 85% as well, and I never noticed noise due to this, would love to see an example, Artur.