Although it's undocumented, CGI's redirect method appears to accept cookies just like it's cousin, the header method.

if (...successful...) {
   print redirect( -uri    => "policy.cgi",
                   -cookie => [ $to_set1, $to_set2, $to_set3 ] );
} else {
   print header( -cookie => [ $to_set1, $to_set2, $to_set3 ] );
   ...
}
[download]

I don't know if cookies can be set on a redirection, but there's no harm in trying.

By the way, the value of the Location field (and therefore the value for the -uri parameter) must be an absolute URI according to the HTTP spec and the docs for the CGI module. policy.cgi is not an absolute URI. Absolute URIs start with something like http:// or ftp://.

Update: Added last paragraph.