I had this issue for a long time with an Exchange account I was using on IMAP. I searched a ton of forums and couldn’t find a solution, but finally found something on TechNet. I wanted to re-post what I found there in case it is of use to anyone else out there.
The error you may receive is: Failed to update headers.
Details: An IMAP command failed.
This error for me occurred any time I tried to do anything in the inbox. Every time I received a new message, etc. According to the technet forum post, it will occur on any client (Thunderbird, Fetchmail, etc).
Unfortunately, what I have is not a solution as this appears to be an MS issue that is as yet unsolved. But, at least it is a way of dealing with it.
IN SHORT, THE WORKAROUND IS: To open your e-mail in Outlook Web Access (OWA), or via Exchange, and delete any meeting requests in your inbox.
It has nothing to do with your client, or hot fixes, or your firewall or your antivirus. All the results you will find on Google to this question are bogus, except for this one now. This is an Exchange problem. The “workarounds” are useless and do not solve anything. You also can’t search the message in the Exchange trace tool by the id listed in the Event log. Awesome!
A client of mine was using using Outlook 2007 connecting to an SBS 2003 server will all service packs. It got the error message “failed to update headers”. I got a similiar error messages when using Thunderbird to connect. On my SBS server the event log was filling up like crazy with Error 1023 every time my user connected, which indicated a server problem. She also could not purge deleted messages. They just stayed in her inbox with a line through them.
As stated by Mike Shen, the problem is caused by Exchange server failing to render the message according to the RFC822 standard. This is your main clue. Howerver, the solution proposed on this forum was overly complicated, dangerous (as it requires you to mess with the delicate Exchange message store) and does not work with SBS, as another poster noted. I needed a simpler solution and found it!
The answer is quite simple:
Dump your entire inbox and all subfolders to a pst, so you have a backup. Then set up the user’s account as an Exchange connection on another computer (my client can’t connect to exchange via MAPI, which is why she is IMAP, so I had to use a different machine and a different Outlook). You could probably also use OWA. I then DELETED every mail in her inbox via the MAPI connection (OWA would probably work too). I then went back to her computer, opened her Outlook and voila, no errors! I then opened backup PST so she could see her old mail. In this case it will act just like an Archive folder. I did not reimport the mail, as I was afraid the errors would reoccur.
The horrible irony of this is that the offending messages were Outlook meeting requests! In other words, Exchange can’t render email properly from it’s own client! YEAH! How do I know this? I know this because I tried to purge all of her messages via IMAP, to no avail. They just stayed in her inbox with a line through them. Well apparently, even though the messages stayed in outlook crossed out, they WERE deleted on the server. When I logged in via the Exchange configured Outlook client, only the two offending messages remained. And both of them were unaccepted meeting requests. Yeah MS! You outdid yourself on this one. :)
Also, another workaround as per gogilamonster:
“Same here started when I upgraded all my users to Outlook 2007. My Unix users using evolution client configured for IMAP are the most affected when they get a meeting invite it get stuck while downloading emails. My work around was have a server-based rules for affected users to move the calendar invites to a different folder other than the inbox and un-subscribe it from the IMAP folder list. They use OWA to deal with the invites but its a hassle.”