Tasmin,
My guess at this point, but which seems very likely, is that the index was botched during the restore from backup. If doing a total restore from a backup, you should have a backup copy of both the Mail folder, and the com.apple.mail.plist file from the Preferences folder. How was yours done? I think the Envelope Index has problems with more than one mailbox, and that is why Rebuild of one alone would not resolve.
Make a copy of both of these Messages folders, or better yet the entire Mail folder, although, hopefully the next step will fully resolve.
The next step is to remove the Envelope Index file (and any other with Envelope in the name) from the Mail folder. To do this, quit Mail, and then follow the instructions in the article at the link below:
http://docs.info.apple.com/article.html?artnum=303803
If you have any IMAP accounts, then you can remove the IMAP accounts, and they can later be restored, or you can do the drag thing in the article. I do not especially like the support write ups on this, but they give you the idea. When you relaunch Mail after removing the Envelope Index file, Mail will normally announce it is ready to Import your mailboxes. However, it does import anything, but rather reindexes ALL the mailboxes in the Mail folder.
Ask any questions, and don't do anything until you are comfortable with what must be done.
Ernie