I have about 200 mail folders, and the dev version of gnus now starts up in about 5 seconds, whereas the version included in Emacs 23.2 took about 1 minute during IMAP session bring-up. Refreshing the group view is now quite fast for me, too.
I believe that nnir has been rewritten from scratch. Doing a 'G G' search against my dovecot server on a folder with several hundred messages takes only a couple of seconds. The new nnir also has support for various kinds of search filters, including a mode where you can type a raw IMAP search string, if the included filters aren't sophisticated enough for your queries. Unfortunately, it's not well-documented yet, so you have to search the mailing list or read the .el file to discover what it can do, at the moment.
Anyway, try the development version of gnus, and see if addresses any of your complaints.
The notmuch application sounds very useful. Searching my mail has been the other big pain point which often leads me to resort to another client.