So it turns out all kinds of stuff fails when your locking calls fail.
Dovecot can’t create indexes of your mailboxes. It also spits out a IMAP warning about it, and mutt pauses a second to display this warning.
mutt can’t create its header cache without it, making the use of IMAP with large mailboxes pretty unbearable.
I’ve made some changes so that now the things that require locking happen on the local file system, and things seem to be happy now.
BTW, mutt is way faster then wanderlust. I guess I can just get used to vim again.