Kadu,
A microsoft não recomenda mais do que 2500 - 5000 itens por pasta dentro do Exchange. Na verdade esse é um dos ítens que mais impacta em performance, por isso você está experiementando esses travamentos.
Não existe uma melhor prática em relação ao Hardware para esse caso, mas com certeza ter 30 000 itens em uma pasta está fazendo a diferença na execução da pesquisa.
Separe esse ítens em múltiplas pastas para que a performance não seja tão impactada durante as pesquisas, o número ideal no seu caso depende do monitoramento de performance do servidor para saber qual vai ser o seu limite.
