Alas, the ability to complete an email address without you finishing typing it, is not linked to your address book. It simply means you've emailed that person before and Outlook automatically keeps a shortcut for you. They need not be in your address book for that to happen.
It sounds to me that you need to copy the address book from you old machine onto your new machine. I could probably do it, but am not confident enough to walk you through it. Perhaps now that others are logged in here for the evening, one of them will help you.