This was transiently scary.
My wife's email is setup on two computers. Both use IMAP.
On the iBook, running OS X 10.3.9, her Mac OS X - Mail (Mail.app) IMAP account is set to view messages and delete permanently when deleted on the iBook. Since 'store sent on server' and 'store draft on server' don't work with our ISP's IMAP implementation, every message she sends defaults cc to herself. BTW, if you drag a message from a local store to the inbox it vanishes forever. God knows where it goes.
On the iMac, running 10.4.6, her Mail.app IMAP account is similary configured. The idea is she drags messages from her inbox when she's done with them to a local folder on the iMac. The messages are thus removed from the IMAP server.
She can thus work her email from two machines, but archives it at one machine.
Except today, after doing some IMAP work, every archival message on the iMac displayed the same error message -- basically saying that only the header was stored locally, the message itself was on the IMAP server and I needed to reconnect. Except, of course, it wasn't.
I quit Mail.app and went for a walk. When I returned I tried again. All of the messages were back again.
PS. I've never done much with Mail.app. Today, when configuring my wife's email, I started using Smart Folders. The ability to create and chain these Boolean queries (iTunes can chain queries, Mail.app can chain queries, iPhoto cannot) is very impressive. Thanks to Spotlight they update instantly. I'm setting up her email to work rather like Gmail, but Mail.app is missing Gmail's ability to attach tags to messages. On the other hand Mail.app has a far superior query language and powerful rules, which can include AppleScript extensions. Mail. app may not be rock solid, but it is certainly very powerful.