I would make the CGI create a new process for the long operation. Write the PID of the new process to a place where a later CGI call can find it (i.e. database). Use some kind of IPC to ask the long-running process for its status, to abort it, and so on. OLE could work, or local TCP or UDP sockets. But this may be a little bit too simple, because it does not take the system load into account.

Another way would be a permanently running daemon / Windows service. That service has to implement an IPC interface (OLE, local TCP or UDP sockets). The CGI is just managing that service; when a new long job has to start, it just tells the service to start the job. The service decides when and how to start the job.

Robustness w.r.t system restarts as you describe it is not too hard with the service way, as services can be set to auto-start. If you mean that jobs aborted due to the reboot have to be restarted, you need to track the job statuses in the service.

If you want to delay the startup until the webserver runs, the web server has to notify the long job service. mod_perl offers a startup hook that could do this.

Alexander