If you happen to install W3C Validator via apt-get on Ubuntu 12, it’s likely the cgi isn’t registered as cgi. Turns out there is a path typo at LocationMatch in /etc/w3c/httpd.conf
<LocationMatch "^/+w3c-markup-validator/+(check(/+referer)?|feedback(.html)?)$">
It should become
<LocationMatch "^/+w3c-validator/+(check(/+referer)?|feedback(.html)?)$">
then everything is back to normal.