Most CGI scripts or their servers include a header that defines the page given from the CGI as a no-cache page. Couple that with a specific expiration date (generally a date that has already passed so that no-caching ever happens) and you have those issues.
I believe the headers usually come from the cgi. But, sometimes the server will tack that on for cgi executions. So, depending on the lib you are using (if any), you should be able to change the CGI.
There is one thing I don't understand. Somehow servers respond differently to SSI, PHP, mod_perl or CGI generated pages. Search engines will not cache these pages, even though no headers are specified. Ditto goes for browsers. I think certain servers might add some header crap-o in. I would like a little insight on this if anyone has a clue.