I dont recall this happening in Outlook, what version of Outlook are you using? Express, Office, 5.5, 6.0, the one that came with Vista, Live Mail (BETA)?
As I recall, you must have a contact in your address book to see their name appear as you type a new email.
Delete the contact from your address book, if you dont want them there.
You might also try (since Outlook is related to Internet Explorer, cousins) going to:
Start> Control Panel> "Internet Options"
Find "Content", and click "Autocomplete"
Disable auto-completion of "forms"
This may disable autocompletion on the To: field in email