Additionally, if if is a fresh folder open (not cached anywhere), the first 2,000 or so message headers load quickly, it slows down to between 200-500/sec for the next few thousand, and if you let it get above several tens of thousands, it continues to slow even more, down to less than 100 headers per second.
So you have 10000+ files in a single folder?
Unless something has changed in WAFL, there's no general index on the directory (I think there's a small hash, but that's not useful for large lookups), so the linear lookup for each one before it gets cached can get large. Can you ask your local mailer to create a second level of directories to reduce that number a bit?
Once cached, the directory access isn't an issue, but when you're scanning every single file in the directory, I'm guessing it doesn't pre-fill.
In my current life, I have 15K mailboxes and 3.2M files on the filesystem.
I find the NetApp boxes to be more than adequate for handling of Maildir formatted mailboxes using Postfix as the MTA, either virtual or maildrop as final delivery agent, and Courier-IMAP as the end user access to the filesystems.
What's the maximum number of files in a folder? I would think that could be a performance issue during a scan.