So unless I'm missing something embarrassingly essential, polyreduce doesn't seem to work properly. Attached is a screenshot of on object reduced to 1000 polys (which appears correctly in the viewer about 1000 polys) yet in the network view it's listed as:

Points 578
Primitives 93,528

I am not sure what's going on. Any ideas?

H 18.0.465

I'd assume your incoming geo has some degenerate polygons, so those are probably just passed on
try using Facet SOP before PolyReduce and check Remove Degenerate
or similarly Clean SOP that has that option on by default