Eu não entendo o porquê, mas funcionou depois que eu mudei:
de
Alias / /var/www/localhost/cgi-bin/ws
para
Alias / /var/www/localhost/cgi-bin/
Além disso, limpei meu .htaccess
apenas para deixar as coisas mais bonitas (removi a verificação de arquivos e diretórios existentes):
RewriteCond %{REQUEST_URI}::$1 ^(/.+)(.+)::$
RewriteRule ^(.*)$ - [E=BASE:%1]
RewriteRule ^(.*)$ %{ENV:BASE}wc [NC,L]
Se alguém entender por que funcionou, explique nos comentários ou em outro lugar. Eu sinceramente acho que a configuração do Apache é uma grande bagunça, ou está muito acima dos meus conhecimentos.