Stencil buffer artifacts

[xernobyl]

I'm getting some strange artifacts when enabling a stencil test. When I remove the test everything looks fine like it's supposed to (other than the stencil op). The stencil buffer is properly clean, and written.

http://web.ist.utl.pt/tcf/rand/stencilcrap.png
2x crop

Any ideas on why this is happening?