The message state database size can be increased to help out if the users has alot if emails they are tracking.
I have increased mine to 500 and it seems to do a much better job now.
increase it by 100 and check performance on the BES before jumping to a high number
read more here about it
View Document