I also have large mail accounts with Mail and haven't had any problems either. iPhoto is the big one I have a beef with, but Mail was always good to me (except with Exchange integration, but DavMail fixed that up).
I am jealous. 10000 messages and it very often takes 5+ seconds to switch between smart mailboxes. Admittedly the smart mailbox filters I have set up are pretty crazy but still... It's not like email metadata changes. The results should be cached.