Hi !!
just looking at _list_headers i noticed that deleted headers are also cached, is there any reason for that ?
Also problems related to users having lots of emails in the inbox folder cause big problems, just about 1000 messages in a user inbox causes that the login process lasts forever. If in safe_mode and execution time and memory usage are limited users with big inbox are totally unable to login. Supporting server side message sort will improve performance and would simplify fetching only one page of headers at a time.