First try going to the Composing section of Mail's preferences,a nd then uncheck the option to "Automatically complete addresses."
If this does not help, then try opening your address book (Contacts) and select all contacts and then choose the option to export them as a Contacts Archive from the File > Export menu (save them to your desktop). Then quit the Contacts program and go to the Go menu in the Finder, hold the Option key and choose the Library option that appears, and then open the Application Support > AddressBook folder. In here, locate and move the AddressBook-v22.abcddb file to your desktop. Then relaunch the Contacts program and press Command-O to re-import your contacts from the saved archive.
When finished, try relaunching Mail to see if the problem persists.