Unfortunately the answer is YES! MS-Outlook 2010 DOES exhibit this rather annoying problem.

And YES, the "fix" seems to be to go into your contacts, delete the email address of the contact bouncing back (the "Display As" field should automatically be deleted). Re-enter the email address from fresh. The "Display As" field should read "Contact's Name (contact@emailaddress.etc)." Save and Close contact.

Once you have done this, you will be able to accept quick-recommendations from Outlook for that contact in the "To:" bar just by typing the first few letters of their NAME. You will note that whereas before the quick-recommendations only showed an email address (and were undeliverable), it now shows "Contact's Name (contact@emailaddress.etc)." It seems, perhaps, that Outlook was unable to cross reference a quick-select email address alone with the Contact's info stored in the address book, whose entry is based on Contact's name as stored in the database.

As for why mine started doing this all-of-a sudden? I am no techhie, but my problem began after syncing my contacts to my new HTC Desire cell phone (running Google Android 2.1). My guess is something got corrupted in that process. HTC Sync is buggy as hell. The software engineers must have cut their teeth programming for Microsoft.