Okay, so first off, this error CLEARLY started for me right when I was running low on space on my phone, so keep that in mind when it comes to avoiding the issue in the future.
Anyway, after scouring the internet, I have found an alternative work around that is substantially better than the option of deleting the Exchange account from the phone and readding it. That option trashes a lot of settings that take forever to restore. The steps below do not avoid all such problems, but do avoid many. This still isn't fixing the underlying problem, which is something HTC needs to get on, but it is a viable work around.
So, what you need to do is to have your Exchange admin simply use the MobileAdmin tool on the Exchange Server to delete the partnership with your device. Once that is accomplished, your phone will reconnect with the Exchange Server just fine again. You may have to recreate some links between contacts from various sources (not sure on this yet), but most everything else seems to work without a lot of starting over.
If you are your own Exchange admin, or if your Exchange admin doesn't know anything about the MobileAdmin application, you can download the file here:
Download details: Microsoft Exchange Server ActiveSync Web Administration Tool
and there are instructions in the folder created when you unzip, or you can go here:
Microsoft Exchange ActiveSync Mobile Administration Web Tool
Just run the downloaded file on the Exchange Server to unzip, run the .msi file from the unzipped folder, open IE on the Exchange Server and navigate to
https://localhost/MobileAdmin, and sign in using the admin account for the Exchange Server. Once you are in, you go to the Remote Wipe link, enter the username of the user with the phone having the problem and click the green arrow, and it will bring up a list of the mobile phone associations that have been created for that user (mine showed my two prior Windows Mobile devices and my prior Palm Pre, in addition to the current Android). Find the Android listing, and click on "Delete" and it will remove the partnership, allowing the phone to create a new one on the next sync.
When you do that next sync, the inbox will go blank, and then will re-download every e-mail for the period that you have selected. You will get new e-mails and the sync protocol issue is gone--at least until the next time your phone starts to fill up. See my next post for my rant about that issue.