Just thought I'd share what I have found out for my Squirrelmail install and it may help you.

When compiling php ( php 4.4.4 ), I used the mhash option:
  ./configure --prefix=/usr/local/apache2/php --with-mhash --with-ldap --with-apxs2=/usr/local/apache2/bin/apxs --with-config-file-path=/usr/local/apache2/php
The --with-mhash PHP option flag *really* sped things up a lot.
Mailbox with 500 messages takes 3 seconds to come up on my PDA.

The other options are specific to your server so just add the --with-mhash option to the rest of your options when compiling PHP for your install.

I still want 'server sort' stuff as well, just thought I'd mention that the 'mhash' option may help you if you aren't already using it. ;-)