...well, let me ask this:
1. What version of Outlook are you using?
2. Is the contacts folder set to be used as an email address book?
3. Are you using contacts or the address book?

Outlook's autocomplete does not work like Outlook Express'. It does not look names up in the address book as you type them. Instead, Outlook builds an autocomplete list of names as you use them. For names not in the autocomplete list yet, it performs autoresolution on names after you have typed them into the To box and moved on to other tasks involved in creating the message. For example, if you have never sent a message to John Doe and you type "john d" into the To box, after you tab away from that box, say to type the Subject and message body, Outlook performs a background lookup and will see if there are any "John D" contacts. If there is only one, it should resolve it and underline the full name. If there is more than one, you may see a red squiggle under the name. That's a signal that you can right-click the name and choose which address to use.

If none of that happens, then when you click Send, Outlook will either resolve the partial name against the address book, if it's unique, or will prompt you to select the name to use.