While your suggestions all are valid to some degree, I think you overlooked one very important point. I can swap out the latest version of RoundCube with Squirrelmail 1.5.x and there is a huge increase in speed - almost
It sounds like Squirrelmail 1.5.x may finally be only pulling the headers for a single "page" of index data? If so, I need to investigate it.. :-)
Given the GUI nature of RC, I'm not sure how practical that is. Unless you allow scrolling right away, perhaps with dummy data, and dynamically fetch the entries you need to show for the current page, as you scroll to them; and used some kind of persistent connection from the client to the server, to avoid bashing the imap server.
Few clients actually get this right (non-web); pine and mulberry (RIP) are the only couple I know that only fetch the index headers for what needs to be shown *now*; both fetch more on demand; and they usea persistent connection (but that's cheating, since they aren't a web app).
List info: http://lists.roundcube.net/users/