Isso pode não ser algo que você pode ou quer fazer, mas o Thunderbird 3.1 funciona bem com grandes bancos de dados. Minha caixa de entrada é de 7 GB e é muito rápida.
A outra coisa que faço é a cada dois anos, pesquiso e encontro todos os e-mails em massa e os excluo. 5000 e-mails de e.newegg.com podem ocupar um pouco de espaço. Mas nunca apago nenhum outro tipo de mensagem.