I just wanted to say that I ahd the same problem, and this came up on my google search. I fixed it by removing the Email Mega Mix patch, which includes Outlook style formatting.
hooked up to Exchange 2003 via activesync
could not reply to emails. could recieve fine, and could even create a new email and send it fine, but if i replied it would hang in the outbox and eventually receive an ambiguous error.
removed mega mix and it started working right away.
i work in IT and have access to the server and tried quite a few things before removing the patch, none of which worked. i have actually had the patch for a LONG time with no problems... until now.