The WDG html validator meets the FOSS requirement and might meet the other requirements, too.
The previous link explains difference between W3C html validator and WDG one.
Here is a link to the license message and code:
http://htmlhelp.org/tools/validator/source.html.en
Since it is written in perl, perhaps it will work with nscgi.
cheers,
