Não sei o que pode estar errado na sua configuração. Como você tem ScriptAlias
env configurado?
Eu testei com a configuração abaixo e tudo parece estar bem no Apache 2.4.10:
<VirtualHost 10.44.0.3:80>
DocumentRoot "/vat/www/mysite"
ServerName mysite.example.com
ErrorLog "/var/log/apache2/mysite.example.com-error_log"
CustomLog "/var/log/apache2/mysite.example.com-access_log" common
ScriptAlias "/cgi-bin/" "/var/www/mysite/cgi-bin/"
<Directory "/var/www/mysite">
Require all granted
Options Indexes FollowSymLinks MultiViews
AllowOverride all
</Directory>
<Directory "/var/www/mysite/cgi-bin">
Options +ExecCGI
AddHandler cgi-script .cgi
</Directory>
RewriteEngine On
RewriteRule "^/test" "/cgi-bin/test.cgi"
</VirtualHost>
abrindo o link abre o script cgi