Hi,
okay bei der HW sollte die Store.exe eigentlich auch nicht viel CPU-Last ziehen - und schon gar nicht bei der Useranzahl.
Folgende Ansatzpunkte:
1. Ist der Exchangeserver auch DC?
2. Wenn nein, Speicheroptimierung nach http://support.microsoft.com/kb/815372/en-us durchgeführt?
3. Wie lange ist die Maschine schon installiert?
4. Hast Du Volltextindizierung auf den Mialboxen und PFs aktiviert?
Gruss
Frank