There is no provision in HTTP for issuing a 3xx redirect that is not a GET request.

This is not true. There are no provisions in HTTP for changing a GET request into another type of request, but if the original came in as a POST, you can send them to the new resource using a POST.

See section 10.3 of the HTTP/1.1 specs

Now, here're the problems -- some browsers treat a 302 as a 303. 301 (as mentioned in this thread), should NEVER be used under these sorts of circumstances, as it's cachable by proxies, and will tell the proxy or browser that it should NEVER come back to the original CGI. (some search engines will drop the item out of their index if they get a 301)

Now, in the case of a 302 on a POST, the browser is supposed to notify the user that they're being redirected to a new location. Most people don't like this, as it seems like a security problem.

As powerhouse has mentioned that this is specifically being sent to PayPal, I'm guessing that they've run into this issue before, and have solutions for dealing with it. As derby and Corion have suggested, the problem has nothing to do with Perl, as the issue is with HTTP, so more than likely PayPal has dealt with this many times over.