hmm, would it be possible to do this via ajax maybe? ie, user selects the format, query is sent via ajax, and the appropriate document is loaded into an iframe on search.asp for example. you could then pick up the succesful event in your ajax call and appropriately deal with the messages.
You could have the file download as an attachment by adding a header, so that the user's browser remains operational. I realize this isn't exactly what you're asking for; but if you combine this with the interstitial page you are using for the HTML version, it might be an improvement for user experience.
Response.AddHeader "Content-Disposition", "attachment; filename=report.xls"
The user would see the interstitial page with the processing graphic which would then re-post the search form. This would allow the "Processing..." graphic to display until the page popped up with a download prompt for the Excel file.
Update: I tried using an iframe, having the page periodically check the document object and trapping the "interface does not exist" error for when it switches to Excel, but it still locks the browser while the Excel document is downloading in the iframe... I don't think a pure js solution is going to work. After that I think the next best avenue to pursue is (unfortunately) Flash. Good luck.
As far as I know, browsers don't offer you any hooks as to how far a download has progressed. In theory, you could do something on the server side and use AJAX to query the server to see how much of the download has been sent, but I don't know how to do it.
I would recommend looking into modifying your upload method to use something like SWFUpload which allows for JavaScript callback on the code. Once the file is uploaded (assuming you are storing it), I would look into passing the filename and type to your Results.asp page where it would then retrieve it form the file store. It's not as secure as keeping it in memory which you elude to in your question; however, would provide a better user experience and may provide the callback solution you need.
Here's a jQuery plug in example that makes the upload process and SWFUpload integration easy: http://blog.codeville.net/2008/11/24/jquery-ajax-uploader-plugin-with-progress-bar/