I think that part of your solution will be to use no-parse headers (nph). Normally, a CGI script doesn't send anything to the web server until the page is complete, which can give you a timeout problem. No-parse headers allow you to send data directly to the browser and prevent the timeout (You set up a Script is started... page and add more dots -- or whatever -- every few seconds.)

A recent article on splash pages with search engines may be applicable as well: How do I create a splash page in Perl.

Update: Changed process->parse to correct error.