> Basically, building a mail index for UID<->MSN translation that can serialize to disk, which would explain how it doesn't necessarily need absurd amounts of RAM and can select fast

That does explain why indexes can get corrupted and need to be cleared out, and why load balancing IMAP can get tricky.