I’m using stencil buffers to do shadows in my engine, and have gotten the algorithm down pretty well. The stencil volumes are getting pretty optimized (in terms of geometry), yet my framerate still takes a big hit. Are the INCR/DECR operations simply slow for geometry?
It’s expensive because they can be really large and you do twice(front faces, back faces).
You can optimise it with scissoring.
There was a thorough discussion of it when Cass and Mark Kilgard released their paper.
Just search for any message with cass in it in 2002 and you will get all the threads.
Just for piece of mind (oops, reading to many Iron Maiden lyrics 
), you’re using 32 bit color depth and 24/8 bit z/stencil, right?
16 bpp might fallback to software emulated stencil.