Something I've figured out, after suffering from Mail's dreaded "missing message" error:
The message from [name/address] concerning [title] has not been downloaded from the server. You need to take this account online in order to download it.To resolve this problem, this recent hint works very well. But in my case, further 'clean up' steps seemed to be needed. I've tried out the following steps on my mail, and it really tidies up and speeds up Mail's performance, and saves a lot of disk space too! Please note that this method will remove any attachments on messages in the mailboxes you clean up...
Open up a mailbox (turn on the Attachments column first), and then sort by Attachment. Or just select all (Command-A), and strip all attachments from all messages in that mailbox. Select all the files with attachments needing to be stripped, and under the Message menu, select Remove Attachments. Once that's done, it seems there's some rather odd behaviour in Mail. At this point, if you were to use the Mailbox: Rebuild command, all the attachments seem to "come back." Strangely, no file-size improvement is seen, even if you do not do a rebuild. However, continuing on...
Create a new mailbox (with the same name, but just add a "2" or something on the end of the new name). Select all of the messages (Command-A) in the "old" mailbox. Use the Message: Copy To menu command, and copy all the messages into the new mailbox you've just created. Note, do not use the Move To command, as that doesn't seem to work properly -- it's probably just linking the old files to the new location, like an alias.
Switch to the new mailbox, and do a Mail: Rebuild command on it. In the Finder, the new folder's file size decreases dramatically, and general responsiveness of that new mailbox within Mail appears to be much faster. After doing all that, you can delete the "old" mailbox. Finally, rename the new mailbox (control-click on the name of the mailbox, select Rename Mailbox, and delete the "2" on the end of the name of the new mailbox). You want to restore the exact same name as the old mailbox had. This will insure that any rules/filters you have previously created that point to that mailbox will not get "confused" by encountering a different mailbox name.
I've done this to all (over 200) of my mailboxes, for all my various clients and topic mailboxes. This has trimmed out over 85% of the total file size of my Mail folder, and Mail seems to be dramatically faster doing mailbox opening and searching.
Important Note: If you want to keep any of the attachments, particularly on incoming mail, where people are sending you files that you do not otherwise have on your hard drive, you should extract them from the messages first, and save them in a file folder on your hard drive -- not "attached" to mail messages! Only then proceed with the "stripping" of the attachments from the mail messages in (whichever) incoming mailbox is getting the "overhaul."
The final chore is to sort out your "Rules" list, and trim out any rules that point to "non-existent" (deleted) mailboxes. After that, you're done!
Mac OS X Hints
http://hints.macworld.com/article.php?story=20060218120944110