Basta apagar a palavra "Google" na sua pergunta. O IMAP é lento. O IMAP em geral é rápido, mas você pode mexer com ele para diminuir o ritmo.
Portanto, ter mais de 10.000 (até 1.000 +) em uma pasta (a Caixa de entrada é uma pasta) reduz a velocidade para torná-la praticamente inutilizável. Para contornar isso você tem que organizar seus e-mails em pastas e subpastas. Felizmente, o Google esconde essa coisa de subpasta ao renomear o procedimento: no mundo do Google, é um "rótulo". Etiquete e marque seus e-mails e eles entram automaticamente em subpastas. Leia os e-mails lá e não o "All-Messages-Folder".
Outra maneira de torná-lo mais rápido é soltar o Outlook! O Outlook é um dos piores clientes IMAP do mundo. Ele pode lidar com o IMAP, mas não acerta.
Se você agora diz: "Mas eu preciso deles em uma pasta e não quero jogar fora o Outlook!" então eu tenho que dizer: "Reclamar com o Google e Microsoft".