I'm not getting a picture..
A limit of the execution time makes no sense to me..?
If you've to deal with the browser timeout (I didn't formulate my question exact enough) I could think of a script which runs as a server, independent of the web server.
You could start|control|stop the replace script through the web interface.
I'd also say that you've more control over the separated replace script this way,
the replace script could be restarted by a cron script if it's killed,
oy you are able to run the script as another user as the web server/ with an other priority.
[find and replace script]<--IPC-->[webserver cgi sript]
This is at least how I would do this.
beside this, storing the progress of the traversal in a filelist file seems like a good idea to me.