Apache::Session will do the equivalent of the PHP4 wizardry for you in mod_perl.

Another approach would be to do something like an md5sum of $query->query_string . $query->remote_host, and save it in some persistent DB for 'an appropriate time' (possibly until your CGI has completed successfully and displayed the results page...)