I've continued to scour the web, and it seems this is a problem that pops up again and again for folks using synchronous XMLHttpRequests with IE, and this article best explains why:
http://www.blacksquare.co.za/blog/?p=458.
In a few words, IE
intentionally delays rendering layout changes until the entire javascript thread has completed. If you use AJAX synchronously (or SJAX, I should say), the return processing is done on the same thread, so the rendering is delayed until after the response has been processed.
And so the solution, according to this blog post, is simple - don't do it. Use AJAX asynchronously, which, so I keep hearing, is the ideal approach 99% of the time.
So now I'm thinking of taking a different approach. Do the Ajax calls asynchronously, so now rendering is not dependent on a single thread. But rather than appending the innerHTML of a single div with each ajax response as it comes (which all but assures that everything will render out of order), set up some kind of structure beforehand, like a table, and give the TD tags ids that associate them with the ID numbers being processed. The top row's TD has id="1", and the 2nd row's TD has id="2", and so on.
So if I have 10 IDs, the user initially sees a table with 10 rows, each of which read "processing..." or something like that, and then they're populated with their respective response text as the ajax responses come. It won't matter in what order the requests are responded to, because the table is already set up in order. When the batch is done, all the IDs' responses will appear in order.
Fortunately, the app I'm working on already has a page that does something kind of similar using ajax. I'll post the code for a working model once I dig into it a little more.