More than just removing Exchange from the iPhone I also run CalCheck.exe against the users Exchange profile from a workstation.
Our users calendars are extremely messy. The physicians calendars are managed/edited/etc by nearly everyone in the office. Those who need it have the required delegation rights.
The biggest time we notice problems is when someone changes or moves an appointment. Exchange appears to maintain the same calendar entry ID and this causes the iDevices to not make the needed change, as they consider there to be no change. To solve this we've told staff that they can not change/move an appointment, instead they must delete the old one, and create a brand new appointment. This seems to have reduced our problems significantly.
For me, once the Exchange logs indicate that the single entry is stuck, syncing never works again. Removing Exchange and re setting it up seems to resolve it quickly. If not, running the CalCheck hasn't failed me yet.