As I was trying to clear out the folders of the mailing lists I’m subscribed to on my mail account (Apple’s MobileMe, née .Mac), I ran into a bit of a problem: I couldn’t delete any messages from some of the folders; it always failed with a timeout error from the server. These folders were usually quite populated (e.g. ~19,000 messages from cocoa-dev). After contacting support chat, and trying many things both in Mail.app as well as MobileMe’s web-app, my case got escalated.
As it turns out, nested IMAP folders are the culprit! It doesn’t matter if the folders in question are at the top-level, just having any nested folders in the account seems to trigger the “slow path” that leads to the problem.
Now my folder structure is a mess with oddly prefixed folder names, but at least it’s flat, and I can work with my emails again.

TL;DR version: Don’t nest folders on MobileMe’s IMAP servers, stick to a flat hierarchy.