I have mailboxes with over 70-100k messages in them in Mail.app, and they never take longer than about 0.5-2.5 seconds to load up when switching to them (the higher range being when the system is also under load).

I have a few small gripes with Mail.app (it occasionally claims that some messages are unread that aren't, for instance), but nothing I've seen of other mail clients has led me to think they'd ever be better for my workflow.