Shadow volumes can be very efficient if the shadowing object is simple. Difficulties occur when the shadowing object is a complex shape, making it difficult to compute a shadow volume. Ideally, the shadow volume should be generated from the vertices along the silhouette of the object, as seen from the light. This is not a trivial problem for complex shadowing objects.
Since the stencil count for objects in shadow depends on whether the eye point is in the shadow or not, making the algorithm independent of eye position is more difficult. One solution is to intersect the shadow volume with the view frustum, and use the result as the shadow volume. This can be a non-trivial CSG operation.
In certain pathological cases, the shape of the shadow volume may cause a stencil value underflow even if you render the front facing shadow polygons first. To avoid this problem, you can choose a ``zero'' value in the middle of the stencil values representable range. For an 8 bit stencil buffer, you could choose 128 as the ``zero'' value. The algorithm would be modified to initialize and test for this value instead of zero. The ``zero'' should be initialized to ``zero'' + 1 if the eye is inside the shadow volume.
Shadow volumes will test your polygon renderer's handling of adjacent polygons. If there are any rendering problems, such as ``double hits'', the stencil count can get messed up, leading to grossly incorrect shadows.