Remember that for users to appear in the directory for outside callers they need to have _both_ the "include in director" checkec _and_ have a recorded voice name.
The Subscriber Information Dump tool can be used to find folks that don't have recorded voice names if you need to find folks like this in a hurry - the latest version of this tool can be found on the http://www.CiscoUnityTools.com.
Also, while you're out there you can go over to the "documents page" and look at the "alternative directory handler prompts" - theres some in there for telling callers to spell a specific number of letters that may be to your liking.
