How to get "Check Names" to read from Contacts

First I'd suggest removing and reinstalling the Outlook Address Book.  Click TOOLS->EMAIL ACCOUNTS->VIEW OR CHANGE EXISTING DIRECTORIES OR ADDRESS BOOKS

Remove the Outlook Address Book, restart Outlook, go back to the same location and add Outlook Address Book back, restart Outlook, and then see if this functionality works now.

I just tried that, but it still is not recognizing the names.

It seems to recognize them if I type in their first name, but not if I use their last name. But I do know it works on the last name because for some reason my fellow IT staff can use last names. I checked to see if all the settings were the same, and they appear to be..maybe I am just missing somethning.

Hmm...well I think I figured out my problem. A while ago I had imported a Personal Address Book into the contacts and this apparently filed all those entries into the first name field only (even though they had last names). So 'check names' didn't see anything in the last name field and therefore wouldn't bring up any results. This is why some were coming up because when you open the contact and click on Full Name button the ones that were imported were showing everything under first name while the ones that were working where showing the first name and last name under the correct fields. Thanks for your help.

I've had a similar problem, whereby users can only search the GAL by last name, but not by first name. We found that this was being caused by Cached mode being enabled in the Outlook 2003 client. Disabling Cached mode solved the problem.