Mailbox format can definitly affect performance (Score 1)

The original posting doesn't say if the server is running pop/imap, and thus if it is used as the final delivery point for those 10,000 users.

If it is, then the hashing of the mailbox path that lucky luck mentioned is worth investigating. Also worth investigating is alternative mailbox formats. If you're using mbox format, then I'm not surprised there's a problem if you have a large number of users (and/or reasonably large mailboxes).

There has been some discussion about these issues on the exim-users mailing list. I read it via egroups.