Perhaps there should be a sort key first, ie default view of inbox, then cache a predefined number of messages and keep that across sessions.
Now if someone wants to resort everything, there's a penalty, unless one guesses which messages to pre-cache for this.. a header index would help since the content of the mail would only need to be retrieved if it's ever clicked on, but quck sorting on date/arrival/from/to etc woudln't use so much mem.
all of these shoudl be config file parameters so users can tweak it according to their usage requirements. a nice default set is fine.
other than that, you can always look at caching packages and see what they do and how they deal with thresholds.. shrug.
-- Robi