When you click on the To button in a new email. The select names windows should open. Where it says Show Names from the: you should have Global Address List in that box. If the users are in your contacts folder, you need to click on the drop down box and select contacts.
Yes, please specify if this is a person in the GAL or your personal contacts. That will help determine where the problem lies. If this is the GAL and you are running on cached mode, try taking your outlook off of cached mode and check again. If you can see the name when you are not running in cached mode then you need to look for errors downloading the offline address book. If this is a personal contact then the solution entails different steps entirely. So please provide those details. Thanks.