Well if the search is taking a long time (and the cgi program isn't written to do something to keep the connection alive) it is possible that the request is timing out. In that case, adjusting the time out probably would help a little. I would just use a different cgi program, if it's not doing something to keep the connection alive.
Like chicken said, if this is being done over SSL, MSIE has intermittent I/O problems with some SSL connections that could be causing the problem.
http://www.netmax.com/fom/cache/307.html