Frankly, a list of tens of thousands of messages sounds completely worthless to me. The first email application I've ever really liked and use all the time is Gmail. I think Google helped to redefine what the email interface should be, so much so that other desktop apps sought to imitate many of their features.
I believe that some of the limitations on performance actually force developers to build better interfaces than what you'd get if a desktop application was built in its place. I have to focus on what is most important and determine the best way to deliver that functionality to you. I suppose that's why I find myself anymore using web applications far more than desktop apps. The only native desktop apps I use anymore are things that I have to have the performance for (IDE's, Photoshop, etc...)