Even given a few annoying things that still exist in the current SVN codebase (some of which I still hope will be fixed before 2.12 is released), 2.12 is much, much better than any previous version. I can't address your "super slow" issue directly, except to say that I definitely try to avoid having too many messages in any given folder; my largest folder is "Deleted Items" with 2300 messages; my largest "regular" folder has <500 messages. I don't know if that's an issue for you.
Running svn head... all of these listed below are exchange via OWA... my inbox and several other folders run 1 to 2K emails constantly ruby-talk has 4.7K a couple have ~2-3K messages I have one folder that holds application generated emails with 12K emails and i've probably got 100+ folders total.. Pentium 4 somewhere around 2GHZ with 1GB ram. Speed isn't an issue for me I rebuild several times a week usually -- basically...$ make distclean; svn update && ./autogen.sh ..params.. && make && sudo make install
first for evolution-data-server, then for evolution, and then for evolution-exchange depending on which ones have had commits...