What server are you using?
The Cyrus IMAP server stores everything in a Berkeley-DB-Structure, is up to now fast and seems to be, claims to be, scalable and it normaly doesn't make a difference if I search/navigate in a small folder, like a project related one (10-100)*x, or the big one containing automated mail 1000*x.
There is a (commercial) Plugin available for Outlook that improves the IMAP support to a noticable degree, /msg me if you're interested, and I ask our Windows-Client guy what it is.
Concerning notes: If you can circumvent this, do it. It is satisfactory, if it works...yeah, well,... if, and generaly a PITA to work with as an admin (IMVHO).
regards,
tomte