Here is the solution I stumbled upon while playing around with the code. First, I removed the -domain=> entirely. Unless I specifically need that, the browser should (and seems to) use the existing hostname/domain without any problem. Second, I removed all of the header that is sent to the browser to set the cookie and replaced it simply with this:

print $query->redirect(-url=>'http://mydomain.com/beta.cgi?c=TestCooki
+e', -cookie=>$cookie_out);
[download]

That has apparently solved my problem. I can use it successfully in MSIE 6, Opera 6, Netscape 4x and Mozilla 1x.