Just tried Dovecot with 85k mails from Linux kernel mailing list, total of 357MB. I mostly wanted to see if the new binary tree file works well. And it does :) Nothing gets slowed down after deleting messages all around the mailbox.
I tried several things with Dovecot, UW-IMAPd and Courier. You'll see that Dovecot is faster in everything else except raw I/O which is a bit strange, have to look why.
I think the most important thing anyway is the time spent opening mailbox. Clients are doing "STATUS mailbox (UNSEEN)" very often and that has to be fast. With Dovecot it's so small that I didn't even bother adding it to the benchmarks, with UW-IMAPd it's 16 seconds, with courier 2 seconds.
Full results can be found at http://dovecot.procontrol.fi/dovecot-benchmark.txt