While the swich to dovecot got us through the end of the year, it wasn't going to be enough long term. We decided to build a new cluster of IMAP servers.
We decided to get four servers with six 15k RPM disks each. Once we got the first server we did some pretty extensive benchmarking. Take a look at the results. We found that our old system could get 142MBps sequential reads and no matter what level of RAID we used the new system can get at least 265MBps. By using RAID 10 we got about three times what our old system could handle (444MBps.) So with all four servers we should have twelve times the disk throughput we had before.
The only thing left to do was distribute the users over the four mail servers. To do that we set up postfix on our MX servers to look up in LDAP what server to forward mail to, and used Perdition to proxy users to the appropriate mail server (again based on LDAP.)
Now that our users are all divided amoung the servers, we can easily migrate someone to a different server by running a script which rsyncs their mail and changes a few settings in LDAP. If we ever need even more capacity we can add another server and just migrate some of the users. When it is time to replace the current servers we can migrate users over with virtually no downtime.