A problem much like this was solved at my work location by having the cgi open a network socket to a daemon running on a dedicated application server and offloading the real work there so the web server could continue processing requests. While the user was waiting (somtimes for up to a minute) we displayed a little "progress bar" that didn't really represent anything other than time elapsed. Seemed to placate our 2500+ strong user base, all of whom had to use the application at least once to accomadate an infrastructure upgrade.