Symptom
Mail prefers the most often used address over the most recently used address when auto-completing addresses.
Solution
When entering an address, Mail selects the most commonly used address based on your usage history of each address in your Address Book.
For example, if choosing between two addresses for the same recipient, Mail will choose the address most often used, not the most recently used.
For more information, see technical document 107202, "
Mac OS X 10.2 Mail: LDAP Search Begins When Second Character In Address Field Entered".