Printing out the environment verified that mod_perl was not running. So, I tried to see if I could get this to work:

<Location /perl-status>
    SetHandler perl-script
    PerlResponseHandler Apache2::Status
    Order allow,deny
    Allow from all
</Location>
[download]

It did. So, after playing with the directives a little I realized the problem was actually with the rewrite rule, mod_perl wanted the location of the rewrite. So, while this did execute, it wasn't running under mod_perl:

  RewriteEngine on
  RewriteRule /s/ /index.cgi [NC,QSA]

  <Location "/path/to/site/docs/index.cgi">
      SetHandler perl-script
      PerlResponseHandler ModPerl::Registry
      PerlOptions +ParseHeaders
      Options +ExecCGI
  </Location>
[download]

And this simple change loaded mod_perl:

  RewriteEngine on
  RewriteRule /s/ /index.cgi [NC,QSA]

  <Location "/s/">
      SetHandler perl-script
      PerlResponseHandler ModPerl::Registry
      PerlOptions +ParseHeaders
      Options +ExecCGI
  </Location>
[download]

Obvious now... but isn't everything in hindsight?