Mail can't delete old email address
Check the "me" card.  Open Address Book, go to the "Card" menu, and select "Go to my card".  Edit if required.  Restart Mail, and send yourself a test email.  Check the from address.

Also, I know you've already checked this, but please check again. In Mail.app, go to Preferences, Accounts, and make sure that the email address is set correctly.