well, a simple example worked for me on ie4linux 6.0.

use strict;
use warnings;
use CGI;
use CGI::Cookie;
my $cgi = CGI->new;
my $w = $cgi->param('w') || 'start';
my $number = $cgi->param('num') || 23;
if ($w eq 'start') {
    print $cgi->header;
    print "<pre>print $ENV{HTTP_COOKIE}</pre>";
    print qq{<a href="/test/cookie_redir.pl?w=cookie">cookie</a>};
}   
elsif ($w eq 'cookie') {
    my $cookie = CGI::Cookie->new(-name => 'ID', -value => $number);
    print $cgi->redirect(
        -uri => '/test/cookie_redir.pl?w=start',
        -cookie => $cookie,
    );  
}
[download]

call it: script.pl?w=cookie;num=1234

edit: sorry, didn't get the POST. i tried my script with POST and it still works on IE.