Some people recommended I take a look at gnus as an IMAP client. I
cheated, since I had most of my gnus setup already in place. Gnus is
like a battleship -- it is big and sturdy, but a bit slow. (It probably
didn't help that I ran it over a forwarded SSH X connection.) It has
good IMAP support, it seems.
Gnus also has this excellent concept of "only show folders with unread
mails in them", this means that I don't get a zillion folders lying
about without anything interesting in them. Listing them is a short L
away, so it's not a big issue to find them when you need them. Also,
autosubscribing to new groups is easy, just add ^nnimap to the
gnus-auto-subscribed-groups variable. It would be nicer if it used
the subscribed list from the server, but evidently, it's not going to do
that.
I guess a screenshot is also in order, so you can see how well-ordered
gnus is, compared to wanderlust.

(And no comments on me having a lot on unread mail, gnus seems to act up
a bit until I've entered all the folders with it, showing the total
number of mails, not the unread number.)
As I got a bunch of feedback from different people about different
clients, I promised to try them and give some feedback on how they
worked.
So, I've taken a look at wanderlust. It's written in elisp, but by some
Japanese. I generally dislike software written by Japanese people as
their docs suck (most Japanese can't write English, it seems), so it is
often difficult to get working. So also with wanderlust. After a bit
of wrestling, I discovered that it was using openssl for handling the
SSL tunnel, while openssl was really unhappy about the fact that my mail
server is using a self-signed certificate. After putting said
certificate into the right place and whacking c_rehash to do the right
thing, it now seems to work fairly well.
Wanderlust is fast, very fast. I really dislike the default folder
overview, mostly for two reasons: it is cluttered:

And there is no way to sort the folders on criteria. I don't want to
maintain a .folders file with all my folders, they are created on
the mail server automatically, and I want my MUA to pick them up as
they appear.
If somebody knows how to customize the folder look a bit, I might stay
with wanderlust. Also, getting it to actually understand that IMAP
folders form a tree would be most useful.