I am having the exact same problem as described by JohnWP in the first post.
That is, mail sync does not work properly after the Android 2.3.5/Sense 3.0 update. When reading, deleting, moving e-mails on my Outlook desktop client, they remain unchanged on my mobile device.
My phone is a HTC Desire HD. Using the HTC stock mail app/widget, and intend to do so. I have done a factory reset and tried all other "solutions" in this thread without any success.
I have contacted HTC about the problem and waiting for a response.