I don't mean to state the "bleeding obvious", forgive me if I am, but there is an option that needs clicking to turn that feature on?
Buggered if I know where it is though......(pause)......
I just looked in Outlook 2007.
Tools/Options/E-mail options/Advanced E-mail options/Suggest names while completing To, Cc, and Bcc fields.
Even if that isn't your problem, I'm damned chuffed with myself for finding it.