Why does OS X Mail fail to recognize that an e-mail address belongs to an existing contact?

Honestly, I believe that this is a bug in mail.app.

I think that if you report it to https://bugreport.apple.com, they'll give you some scripts to run, and will ask you to send some special logs.

I know this isn't a "solution", but maybe it will help improve the app for all of us..

I was having the same issue. To resolve it, I went into the previous recipients list and removed all entries of the offending address, as well as any other email addresses associated with that person. From that point forward, when composing an email it correctly pulled the Address Book entry and not the independent address.

This could be due to entries in your previous recipients list. This list is accessed in Mail via the Window > Previous Recipients menu item.