As fanf2 said, MSNs != UIDs. Also, I didn't mean to imply that MSNs are an insurmountable limitation for performance, they just complicate things a lot.

I'm not familiar with Dovecot's code or very good at reading C, but I think part of how they handle it is here: https://github.com/dovecot/core/blob/81b5b188c478ec36bea8bda...

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, probably at heavy cost when EXPUNGeing old messages. I'm sure there were worse implementations that did just maintain it all in RAM way back in the day, and still some that do (like the one I ran into).