I had a user who's Outlook had apparently deleted the Trash folder from the IMAP server improperly. Outlook functioned okay, but any other email client would barf. The mail client would report a "filesystem error" when you tried to access the Trash folder, and wouldn't delete anything. The server would constantly log:
IOERROR: opening /var/spool/cyrus/mail/j/user/john/Trash/cyrus.header: No such file or directory
I'd noticed the log entries a long time ago, but given that his Outlook was still working fine I didn't stress over it. Now that he's switched to Thunderbird, it became a problem.
The fix was simply to run the following on the mail server:
sudo su - su - cyrus /usr/sbin/cyrreconstruct -rf user.john
If you don't use the dot separator, it would look like:
/usr/sbin/cyrreconstruct -rf user/john
It's a quick and easy fix. cyrreconstruct (or simply reconstruct on some systems) will rebuild the user's entire mail database, and can fix many different types of corruption problems.