Had an issue come through my phone recently where it did not cope well with some updates I was doing on my Exchange account. Essentially I was editing emails and Calendar invites through Outlook Web Access and at the same time editing them in Outlook 2010 using Offline mode. While the Exchange Server was probably just streaming out the changes to the mail store in the order they became visible (so, immediately for the OWA change and when I later VPN’d into the office for the Thick Client), I don’t think the phone coped very well in interpreting the changes and as a result, the mail store got corrupted (of course that’s what the error means!).
Perhaps each update goes to exchange with a time the update was made on the client and the phone was trying to do them in the same order? Not sure… but the easy way to fix it is to deselect the Email from what syncs with the phone, then reselect it – the phone then throws away the mail store and recreates it, losing the corruption in the process.