We may have found the solution.. Seems all of our other users that are in the NEC system that seems to have the Name Directory working are in a Distrubition Group/All..

Reviewing those contacts that are not in the Dis Group.. Under Customize Mailbox.