In the past 2 weeks I have been getting this error message on MOST users machines, not all. Or it will start after a few have connected to the Ex server. The only way I can get it to stop is to restart the Exchange Information Store service on the server.
Could it be my Store is getting too large?
Since I have SP2 I know the store size can be changed,