Outlook 2000 has never had this feature. Autocompletion did not become a
feature until Outlook 2002.
Before Outlook 2002, Outlook only had a feature called auto-resolution. If
you enter part of a name or a nickname then tab out of the field (or hit
Alt-K [Check Names]), Outlook will attempt to resolve the name against your
address book. If it can't, it'll red underline it and you can right click on
the name to manually resolve it. Outlook will save the resolution for future
use.