What if we use a half-lambert lighting model? The shadow will flicker on the edges too, as the light goes beyond N dot L..how would you handle this?

That's an interesting question...

I guess you could try fading away the shadow contribution depending on various parameters, like the distance between the shadow caster and receiver, and the real N.L value.
fade away the contribution when both the N.L value is close to zero and the shadow-caster to receiver distance is small enough?

something like:

ndotlScaler = 1.0f / 0.2; // 0.2 == distance below witch the fading will start
distanceScaler = 1.0f / 0.2; // 0.2 == distance below witch the fading will start
ndotlFader = nDotL * ndotlScaler;
distanceFader = (pixelDepth - shadowDepth) * distanceScaler; // (assuming positive linear depth values)
shadowCoeff = 1.0f - (1.0f - shadowCoeff) * clamp(ndotlFader * distanceFader, 0.0f, 1.0f); // assuming shadow coeff to 0 means fully shadowed, 1 fully lit

?

I'm not sure it would look good enough though...
perhaps just the distance fade would be better. you'd still get shadows from objects in front of the receiver, but it would kind of disable shadows for the receiver itself...

or using a min(ndotlFader, distanceFader) might be better than the mul.
it looks like it would require a lot of tweaking to get right...

by the way, do games that use half-lambert lighting (like team forteress2), actually have self-shadowing objects ?