Recently, Mail's links between emails and their replies in broke, so that clicking on the answered/forwarded arrow resulted in the message Mail was unable to find your response to the message . You may have deleted the message..
After some investigation, I found out that this happened after I have changed the email address in one of my accounts (say from old@server.com to new@server.com). Whatever messages addressed to old@server.com had the Reply/Forward links broken. The process was found to be reversible -- changing the address back made the links for old@server.com work again. However, it messes up with replies to new@server.com and puts the incorrect address into the From field.
The solution was to leave new@server.com in my main account, and create another account with old@server.com as the email address. This makes replies to both addresses work again in all of the accounts (even in the On my Mac mailboxes). The fake account can be offline and completely lack receive/send data, but it has to be active.
Better yet, I have put old@server.com into the account I only use for mailing lists (and hence, never reply there) so that the sidebar in Mail does not grow unnecessarily.
Mac OS X Hints
http://hints.macworld.com/article.php?story=20090203151350814