I have an engine and applications built within it which make rather extensive use of gluTessellator; it's a system based around 2D polyloop graphics which are tessellated before drawing. I've programmed two graphics editing tools for it, and can easily demonstrate the relevant bug using the more "vector-oriented" of the two. (Both are vector, but one mimics MSPaint)
The basic gist is any tessellation job on a one-loop polygon that retains either a positive or negative "turn" value for each of its vertices (for instance, a spiral, if one starts at the center vertex) will not detect "odd" loops under the evident assumption that it's a non-self-intersecting shape. This means the result shape will show up as filled.
There seem to be some other cases as well where the polygon can turn differently and still muck up. Either way, I suspect it's a broken once-over operation which causes the actual work to be skipped.
On another note, I recently updated my development tools and I'm now getting actual crashes from the tessellator when I pass it overlapping polylines; I'm using the new version of Cygwin. I'm assuming until further notice that the instability is an old Mesa implementation or something.