gibt es für das Verzeichnis einen directory oder location-Eintrag?
Was steht dort bei den Options?
nachtrag:
<Location /cgi-bin>
AllowOverride None
Options +ExecCGI -Includes
SetHandler cgi-script
</Location>
ist als standart für virtuelle server ... also auch für meinen wo das script ja funktioniert