Mail slowing you down? Rebuild its database

Help!! Everytime, I open mail app it crashes. I've tried rebuilding, removing the envelope index and various other online suggestions and nothing has worked. As soon as it goes online it crashes. Replacing the mail app from another computer did not work either. I've got several email accounts and a ton of email (14,000). I hate to think that I will never see it again. Does anyone have any suggestions on what could be causing this and how I can resolve the issue?

I only use POP accounts -- no IMAP, no wacky corporate networks, nothing beyond a few email accounts and at least six point eight bazillion messages, and the file size reduction was only 4MB, down to 20MB from 24MB, and within a few hours it had grown back up to 23MB.

OK, it seems the brown labeling is very different from what I thought - my apologies for my reaction then.
I hope you guys will find a solution...

Colt, yep, this is exactly the same brown labeling that I get too when rebuilding. (It's not the spam labels)

The only way I've been able to get rid of the brown is use Mail Labels applesript. Select the message then use the applescript to label it "none."

http://www.twistermc.com/blog/2005/06/03/labels-for-apples-mail-application

I have approx. 9,000 messages; Envelope Index is ~3 MB. I agree with earlier poster -- if David's Envelope Index was 300 MB, something was/is wrong with his machine.

To everyone else, if your Envelope Index is less than 500k per thousand messages, don't bother with this "tip".

Nope...I'm not talking about messages in light brown text marked as possible spam, I'm talking about dark brown fully-highlghted messages. Highlighted in the same fashion as related messages are (in my case, related messages are highlighted in a light blue). Here's a pic of my "brown mail" http://www.coltwest.com/brownmail.jpg Anyone know what this is all about? I can't change the color. It hasn't been marked as spam, flagged, etc. It's just brown!

Does anyone know what this will do to MailTags 1.2.1 metadata?

FWIW: I did this and rebuilding for over 72,000 messages took over 20 minutes on my 1.2Ghz iBook G4. Envelope file went from 31.9MB to 29.5. I did this b/c Mail seemed to be kind of slow so I thought it might be worth it if I gained some speed. I haven't noticed any speed difference.

messages in brown, as mentioned by posters #5 and #11, are messages that are considered to be possibly spam. I.e. they fit the spam recognition rules. You can improve these recognition rules by deciding on these brown-marked mails, if they are spam or not. How to do that (open the mail? preview it?) I don't remember, but I do remember it is fairly easy and logical.

I am also really curious if 'Rebuild Mailbox' has the same function as this tip, as mentioned several times before. Does anyone know?

I had a problem where I couldn't move a message from junk into my inbox without crashing the mail app (unless I set a rule). I seemed to be a lone person with that issue. I followed the above and all works great. Glad to see this posted.